Submission #1045323

#TimeUsernameProblemLanguageResultExecution timeMemory
1045323LoboJoker (BOI20_joker)C++17
14 / 100
2056 ms32004 KiB
#include<bits/stdc++.h> using namespace std; const long long inf = 1e18 + 10; const int inf1 = 1e9 + 10; #define int long long #define dbl long double #define endl '\n' #define sc second #define fr first #define mp make_pair #define pb push_back #define all(x) x.begin(), x.end() mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count()); const int maxn = 2e5+10; const int B = 1; int n, m, q, col[maxn], colc[2*maxn], ansl[maxn]; vector<int> g[maxn], gc[2*maxn]; pair<int,int> edg[maxn]; bool okcol; void dfscol(int u) { for(auto v : g[u]) { if(col[v] == -1) { col[v] = (col[u]^1); dfscol(v); } else if(col[v] != (col[u]^1)) { okcol = 0; } } } bool okcolc; void dfscolc(int u) { for(auto v : gc[u]) { if(colc[v] == -1) { colc[v] = (colc[u]^1); dfscolc(v); } else if(colc[v] != (colc[u]^1)) { okcolc = 0; } } } void solve() { cin >> n >> m >> q; for(int i = 1; i <= m; i++) { int u,v; cin >> u >> v; edg[i] = mp(u,v); } int bLl = 0; int bLr = min(m+1,B-1); int bRl = 1; int bRr = min(m+1,B); while(bLl != m+1) { for(int i = 1; i <= n; i++) { g[i].clear(); col[i] = -1; } for(int i = 1; i <= bLl-1; i++) { int u = edg[i].fr; int v = edg[i].sc; g[u].pb(v); g[v].pb(u); } for(int i = bRr+1; i <= m; i++) { int u = edg[i].fr; int v = edg[i].sc; g[u].pb(v); g[v].pb(u); } int cntcol = 0; okcol = 1; for(int i = 1; i <= n; i++) { if(col[i] == -1) { colc[cntcol] = -1; colc[cntcol+1] = -1; col[i] = cntcol; cntcol = cntcol+2; dfscol(i); } } int L = bLl; int R = bRl; while(L <= bLr and R <= bRr) { vector<int> verts; for(int i = bLl; i <= L; i++) { if(i == 0 or i == m+1) continue; int u = edg[i].fr; verts.pb(u); int v = edg[i].sc; verts.pb(v); gc[col[u]].pb(col[v]); gc[col[v]].pb(col[u]); } for(int i = R; i <= bRr; i++) { if(i == 0 or i == m+1) continue; int u = edg[i].fr; verts.pb(u); int v = edg[i].sc; verts.pb(v); gc[col[u]].pb(col[v]); gc[col[v]].pb(col[u]); } for(auto i : verts) { gc[col[i]].pb((col[i]^1)); gc[(col[i]^1)].pb(col[i]); } okcolc = 1; for(auto i : verts) { if(colc[col[i]] == -1) { colc[col[i]] = 0; dfscolc(col[i]); } } if(okcolc == 1 and okcol == 1) { ansl[L] = R; L++; } else if(R == m+1) { ansl[L] = inf; L++; } else { R++; } for(auto i : verts) { colc[col[i]] = -1; gc[col[i]].clear(); } } bLl = min(m+1,L); bLr = (min(m+1,bLl+B-1)); bRl = min(m+1,R); bRr = min(m+1,bRl+B-1); } for(int i = 1; i <= q; i++) { int l,r; cin >> l >> r; if(ansl[l-1] <= r+1) { cout << "NO" << endl; } else { cout << "YES" << endl; } } } int32_t main() { ios::sync_with_stdio(false); cin.tie(0); int tt = 1; // cin >> tt; while(tt--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...