Submission #1093541

#TimeUsernameProblemLanguageResultExecution timeMemory
1093541ntdaccodeJoker (BOI20_joker)C++17
39 / 100
2068 ms69604 KiB
#include<bits/stdc++.h> #define fori(i,a,b) for(int i=a;i<=b;i++) #define int long long #define ii pair<int,int> #define fi first #define se second #define pb push_back using namespace std; const int mod=1e9+7; const int M=1e6+10; const int N=1e3+10; int n,m,q; int x[M],y[M]; vector<int> ke[M]; int dd[M]; bool dfs(int u,int p) { for(int v:ke[u]) { if(v==p) continue; if(dd[v]) { //cout << dd[v] << " " << dd[u] << "\n"; if(dd[v]%2==dd[u]%2) return true; } else { dd[v]=dd[u]+1; if(dfs(v,u)) return true; } } return false; } bool check(int mid,int idx) { fori(i,1,idx-1) { if(x[i]==y[i]) continue; ke[x[i]].pb(y[i]); ke[y[i]].pb(x[i]);//if(mid==5) cout << x[i] <<" " << y[i] << "\n"; } for(int i=mid+1;i<=m;i++) { if(x[i]==y[i]) continue; ke[x[i]].pb(y[i]);//if(mid==5) cout << x[i] <<" " << y[i] << "\n"; ke[y[i]].pb(x[i]); } fori(i,1,n) dd[i]=0; bool ok=0; fori(i,1,n) { if(!dd[i]) { dd[i]=1; if(dfs(i,i)) { ok=1; break; } } } //cout << ok << " "; fori(i,1,n) ke[i].clear(); return ok; } vector<ii> Q[M]; int ret[M]; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define task "1" if(fopen(task".inp","r")) { freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } cin >> n >> m >> q; fori(i,1,m) cin >> x[i] >> y[i]; int mx=0; fori(i,1,q) { int l,r; cin >> l >> r; Q[l].pb({r,i}); mx=max(mx,l); } // check(5,4) ;return 0; fori(i,1,mx) { if(Q[i].size()==0) continue; int l=i,r=m,lim=0; while(l<=r) { int mid=(l+r)/2; if(check(mid,i)) { lim=mid; l=mid+1; } else r=mid-1; } //cout << lim << " "; for(ii v:Q[i]) ret[v.se]=(v.fi<=lim) ; } fori(i,1,q) { if(ret[i]) cout << "YES\n"; else cout << "NO\n"; } }

Compilation message (stderr)

Joker.cpp: In function 'int32_t main()':
Joker.cpp:77:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:78:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...