QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#252502	#6679. Not Another Path Query Problem	fzx	WA	25ms	13868kb	C++14	1.1kb	2023-11-15 20:18:00	2023-11-15 20:18:01

Judging History

This is the latest submission verdict.

[2023-11-15 20:18:01]
Judged

Verdict: WA
Time: 25ms
Memory: 13868kb

Show

[2023-11-15 20:18:00]
Submitted

answer

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int INF=1e6+5;
const int INFN=1e5+5;
int n,m,q,v,x[INF],y[INF],z[INF],vis[INF],fa_set[INF],d[INFN][75];
int find_set(int x) {return x==fa_set[x]?x:fa_set[x]=find_set(fa_set[x]);}
void mer(int x,int y) {x=find_set(x);y=find_set(y);fa_set[x]=y;}
signed main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m>>q>>v;v--;
	for (int i=1;i<=m;i++)
		cin>>x[i]>>y[i]>>z[i];
	int ba=0;
	if (v>=0) { 
		for (int i=60;~i;i--) {
			if (v&(1ll<<i)) ba|=(1ll<<i);
			else {
				vis[i]=1;
				ba|=(1ll<<i);
				for (int j=1;j<=n;j++) fa_set[j]=j;
				for (int j=1;j<=m;j++)
					if ((z[j]&ba)==ba) mer(x[j],y[j]);
				for (int j=1;j<=n;j++)
					d[j][i]=find_set(j);
				ba^=(1ll<<i);
			}
		}
	}
	for (int j=1;j<=n;j++) fa_set[j]=j;
	for (int j=1;j<=m;j++) mer(x[j],y[j]);
	while (q--) {
		int x=0,y=0,fl2=0;
		cin>>x>>y;
		if (find_set(x)!=find_set(y)) {cout<<"No\n";continue;}
		if (!v) {cout<<"Yes\n";continue;}
		for (int i=0;i<60;i++)
			if (vis[i] && d[x][i]==d[y][i]) fl2=1; 
		if (fl2) cout<<"Yes\n";
		else cout<<"No\n";
	}
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 13868kb

input:

output:

Yes
No
Yes
No

result:

ok 4 token(s): yes count is 2, no count is 2

Test #2:

score: 0

Accepted

time: 0ms

memory: 13856kb

input:

output:

Yes

result:

ok YES

Test #3:

score: -100

Wrong Answer

time: 25ms

memory: 13868kb

input:

100 2000 50000 0
32 52 69658009083393280
26 38 868250171554967916
87 32 743903879320440454
22 15 19782587273744714
57 98 845866434191429143
42 95 1145336983294966993
67 40 1036117659380117375
46 24 265457274847122243
63 44 438254608190938148
28 23 992625102587165494
57 87 558124114385470345
6 17 535...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

wrong answer expected YES, found NO [1st token]