Submission #858812

#	Time	Username	Problem	Language	Result	Execution time	Memory
858812		iskhakkutbilim	Joker (BOI20_joker)	C++17	39 / 100	2092 ms	24144 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
 
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 2e5;
vector<pair<int, int> > g[N+1];
int n, m, q, timer = 1; 
int used[N+1], lens[N+1];
 
int Left, Right, ok; 
vector< pair<int, int> > query;
void dfs(int v, int par){
	if(ok) return;
	used[v] = timer;
	for(auto [to, idx] : g[v]){
		if(used[to] == timer &&  (idx < Left or idx > Right) && to != par){
			int len = lens[v] - lens[to] + 1;
			if(len % 2 == 1){
				ok = 1;
				return;
			}
		}else if(used[to] < timer && (idx < Left or idx > Right)){
			lens[to] = lens[v] + 1;
			dfs(to, v);
		}
	}
	used[v] = timer+1;
}
 
 
 
 
 
main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	cin >> n >> m >> q;
	for(int i = 0;i < m; i++){
		int a, b; cin >> a >> b;
		g[a].push_back({b, i + 1});
		g[b].push_back({a, i + 1});
	}
	int subtask = 1;
	query.resize(q);
	for(int i = 0;i < q; i++){
		
		cin >> query[i].ff >> query[i].ss;
		if(query[i].ff != 1) subtask = 0;
	}
	if(subtask && max({n, m, q}) > 2000){
		int l = 0, r = m + 1;
		while(l + 1 < r){
			int mid = (l + r) >> 1;
			Left = 1, Right = mid, ok = 0;
			for(int i = 1;i <= n; i++){
				if(used[i] < timer){
					lens[i] = 1;
					dfs(i, -1);
					if(ok) break;
				}
			}
			timer+= 2;
			if(ok) l =mid;
			else r = mid;
		}
		for(int j = 0;j < q; j++){
			if(query[j].ss <= l){
				cout << "YES";
			}else cout << "NO";
			cout << '\n';
		}
		return 0;
	}
	for(int j = 0;j < q; j++){
		Left = query[j].ff, Right = query[j].ss;
		ok = 0;
		for(int i = 1;i <= n; i++){
			if(used[i] < timer){
				lens[i] = 1;
				dfs(i, -1);
				if(ok) break;
			}
		}
		timer+= 2;
		cout << (ok ? "YES" : "NO") << '\n';
	}
	return 0;
}
 

Compilation message (stderr)

Joker.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 | main(){
      | ^~~~

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 25 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29