Submission #1065801

#TimeUsernameProblemLanguageResultExecution timeMemory
1065801Faisal_SaqibToy Train (IOI17_train)C++17
49 / 100
2028 ms2904 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define vll vector<ll> #define pb push_back #define sll set<ll> const int N=5e3+10; vll ma[N]; bool charge[N],alive[N],vis[N]; sll rem; ll n,owner[N],m,deg[N],deg_[N]; sll attr(sll a,ll player) { ll sz=a.size(); for(auto&i:rem) { vis[i]=0; deg_[i]=deg[i]; } // cout<<"Computing attractor of: "; queue<int> q; for(auto&i:a) { // cout<<i<<' '; if(alive[i]) { q.push(i); vis[i]=1; } } // cout<<endl; sll ans; // cout<<"reach: "; while(q.size()) { int f=q.front(); q.pop(); ans.insert(f); // cout<<f<<' '; for(ll&y:ma[f]) { if(!alive[y])continue; deg_[y]--; if(owner[y]==player) { // y have edge to the set a and is own by palyer so he will take the edge if(!vis[y]) { vis[y]=1; q.push(y); } } else // Owned by other player { if(deg_[y]==0 and vis[y]==0) { vis[y]=1; q.push(y); } } } } // cout<<endl; return ans; } sll attrcomp(sll a,ll player) { // We never want to reach any vertex in a // Reach(a) == compliement( Safety( compliment( a ) ) ) // Reach( compliment ( a ) ) == compliement( Safety( a ) ) // compliment( Reach( compliment ( a ) ) ) == Safety( a ) sll cp; for(auto&i:a) cp.insert(i); // if(a.find(i)==a.end()) cp=attr(cp,player); sll ans; for(auto&i:rem) if(cp.find(i)==cp.end()) ans.insert(i); return ans; } sll Buchi(sll a) { ll sz=a.size(); while(true) { auto cur=attrcomp(a,1); if(cur.size()==0)break; // cout<<"Step\n"; // cout<<"For a: "; // for(auto i:a) // { // cout<<i<<' '; // } // cout<<endl; // cout<<"Got cur: "; // for(auto i:cur) // { // cout<<i<<' '; // } // cout<<endl; cur=attr(cur,2); // cout<<"Got cur: "; // for(auto i:cur) // { // cout<<i<<' '; // } // cout<<endl; for(auto&i:cur){ auto it=a.find(i); if(it!=end(a)) a.erase(it); auto it1=rem.find(i); if(it1!=end(rem)) { for(auto jp:ma[i]) deg[jp]--; alive[i]=0; deg[i]=0; ma[i].clear(); rem.erase(it1); } } } return a; } std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) { n=a.size(); sll vertexs; for(int i=1;i<=n;i++) { rem.insert(i); alive[i]=1; if(a[i-1]==1) { owner[i]=1; } else { owner[i]=2; } if(r[i-1]) { vertexs.insert(i); charge[i]=1; } else { charge[i]=0; } } m=u.size(); for(int j=0;j<m;j++) { u[j]++; v[j]++; ma[v[j]].pb(u[j]); // Directed edges deg[u[j]]++; // ma[v[j]].pb(u[j]); } sll answer=Buchi(vertexs); vector<int> ap(n); for(int i=1;i<=n;i++) ap[i-1]=alive[i]; return ap; }

Compilation message (stderr)

train.cpp: In function 'std::set<long long int> attr(std::set<long long int>, long long int)':
train.cpp:16:8: warning: unused variable 'sz' [-Wunused-variable]
   16 |     ll sz=a.size();
      |        ^~
train.cpp: In function 'std::set<long long int> Buchi(std::set<long long int>)':
train.cpp:87:8: warning: unused variable 'sz' [-Wunused-variable]
   87 |     ll sz=a.size();
      |        ^~
#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...