Submission #255955

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
255955	2020-08-02T06:56:45 Z	임성재(#5031)	Joker (BOI20_joker)	C++17	25 / 100	223 ms	16728 KB

Joker

#include<bits/stdc++.h>  
using namespace std;  
  
#define fast ios::sync_with_stdio(false);cin.tie(NULL)  
#define fi first  
#define se second  
#define all(v) (v).begin(),(v).end()  
#define pb push_back  
#define eb emplace_back
#define pre(a) cout<<fixed; cout.precision(a)
#define mp make_pair
  
typedef long long ll;  
typedef pair<int,int> pii;  
typedef pair<ll,ll> pll;  
const long long INF = 1e18;
const int inf = 1e9;

int n, m, q;
int l, r;
vector<pii> e;
vector<int> g[200010];
int d[200010];
int p[200010];

int Find(int a) {
	return p[a] = p[a] == a ? a : Find(p[a]);
}

void Union(int a, int b) {
	a = Find(a);
	b = Find(b);

	p[b] = a;
}

bool dfs(int x) {
	//cout << "//" << x << endl;
	for(auto i : g[x]) {
		if(d[i]) {
			continue;
		}

		d[i] = d[x] + 1;
		if(dfs(i)) return true;
	}

	return false;
}

int main() {
	fast;

	cin >> n >> m >> q;


	for(int i=1; i<=m; i++) {
		int u, v;

		cin >> u >> v;

		e.eb(u, v);
	}

	reverse(all(e));

	for(int i=1; i<=n; i++) p[i] = i;

	for(auto i : e) {
		if(Find(i.fi) == Find(i.se)) continue;

		g[i.fi].eb(i.se);
		g[i.se].eb(i.fi);

		Union(i.fi, i.se);
	}

	for(int i=1; i<=n; i++) {
		if(d[i]) continue;

		d[i] = 1;
		dfs(i);
	}

	for(int i=1; i<=n; i++) p[i] = i;

	int ans = 0;
	
	for(int k=0; k<e.size(); k++) {
		auto i = e[k];
		//cout << "? " << i.fi << " " << i.se << endl;
		
		if(Find(i.fi) == Find(i.se)) {
			//cout << "! " << i.fi << " " << i.se << endl;
			if(abs(d[i.fi] - d[i.se]) % 2 == 0) {
				ans = m - k;
				//cout << "!!!" << ans << "\n";
				break;
			}
			else continue;
		}

		Union(i.fi, i.se);
	}

	while(q--) {
		cin >> l >> r;

		if(r < ans) cout << "YES\n";
		else cout << "NO\n";
	}
}

Compilation message

Joker.cpp: In function 'int main()':
Joker.cpp:89:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int k=0; k<e.size(); k++) {
               ~^~~~~~~~~

Subtask #1
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4992 KB	Output is correct
2	Correct	4 ms	4992 KB	Output is correct
3	Incorrect	5 ms	4992 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4992 KB	Output is correct
2	Correct	4 ms	4992 KB	Output is correct
3	Incorrect	5 ms	4992 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4992 KB	Output is correct
2	Correct	4 ms	4992 KB	Output is correct
3	Correct	137 ms	13288 KB	Output is correct
4	Correct	188 ms	16728 KB	Output is correct
5	Correct	187 ms	14416 KB	Output is correct
6	Correct	135 ms	11752 KB	Output is correct
7	Correct	134 ms	11240 KB	Output is correct
8	Correct	126 ms	9832 KB	Output is correct
9	Correct	165 ms	11420 KB	Output is correct
10	Correct	222 ms	14440 KB	Output is correct
11	Correct	146 ms	11368 KB	Output is correct
12	Correct	198 ms	14184 KB	Output is correct
13	Correct	108 ms	8040 KB	Output is correct
14	Correct	133 ms	9576 KB	Output is correct
15	Correct	184 ms	12648 KB	Output is correct
16	Correct	223 ms	14312 KB	Output is correct