# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1040434 | vjudge1 | Toy Train (IOI17_train) | C++17 | 1082 ms | 4188 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "train.h"
#include<bits/stdc++.h>
using namespace std;
set<int>radj[5010],adj[5010];
set<int>inv(vector<int>v,set<int>st){
for(auto i:v)
st.erase(i);
return st;
}
vector<int>aset(set<int>v,vector<int>own){
vector<int>cnt(5000),don(5000);
queue<int>q;
vector<int>ans;
for(auto i:v)
q.push(i),don[i]=1;
while(q.size()){
int x=q.front(); q.pop();
ans.push_back(x);
for(auto i:radj[x]) {
if(don[i])continue;
if(own[i]) q.push(i),don[i]=1;
else if(++cnt[i]==adj[i].size())
q.push(i),don[i]=1;
}
}
return ans;
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
int N=a.size(),M=u.size();
std::vector<int> res(a.size()),bozo=a;
for(auto&i:bozo)i=!i;
for(int i=0;i<M;i++)
adj[u[i]].insert(v[i]),
radj[v[i]].insert(u[i]);
set<int>charg,hav;
for(int i=0;i<N;hav.insert(i++))
if(r[i])charg.insert(i);
int CC=N;
while(CC) {
vector<int>v=aset(charg,a);
if(v.size()==CC){
for(auto i:v)
res[i]=1;
break;
}
v=aset(inv(v,hav),bozo);
for(auto i:v){ CC--;
charg.erase(i);
hav.erase(i);
for(auto j:adj[i])
radj[j].erase(i);
for(auto j:radj[i])
adj[j].erase(i);
adj[i].clear();
radj[i].clear();
}
}
return res;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |