Submission #789619

#TimeUsernameProblemLanguageResultExecution timeMemory
789619esomerToy Train (IOI17_train)C++17
49 / 100
2047 ms1356 KiB
#include<bits/stdc++.h> #include "train.h" using namespace std; typedef long long ll; //~ vector<int> who_wins2(vector<int> A, vector<int> R, vector<int> U, vector<int> V){ //~ int n = (int)A.size(); //~ int m = (int)U.size(); //~ bool first = 1; //~ for(int i = 0; i < m; i++){ //~ if(V[i] != U[i] && V[i] != U[i] + 1) first = 0; //~ } //~ if(first){ //~ vector<bool> self(n, 0); //~ vector<bool> other(n, 0); //~ for(int i = 0; i < m; i++){ //~ if(U[i] == V[i]) self[U[i]] = 1; //~ else other[U[i]] = 1; //~ } //~ vector<int> ans(n, 0); //~ for(int i = n - 1; i >= 0; i--){ //~ if(A[i] == 1){ //~ if(self[i] == 1 && R[i] == 1) ans[i] = 1; //~ else if(other[i] == 1) ans[i] = ans[i+1]; //~ }else{ //~ if(self[i] == 1){ //~ if(R[i] == 0) ans[i] = 0; //~ else{ //~ if(other[i]) ans[i] = ans[i+1]; //~ else ans[i] = 1; //~ } //~ }else if(other[i] == 1) ans[i] = ans[i+1]; //~ } //~ } //~ return ans; //~ }else return {}; //~ } void process(vector<int>& A, vector<int>& R, vector<int>& U, vector<int>& V, vector<bool>& forced){ int n = (int)A.size(); int m = (int)U.size(); vector<vector<int>> radj(n); vector<int> out(n, 0); for(int i = 0; i < m; i++){ if(R[U[i]] == 1) continue; out[U[i]]++; radj[V[i]].push_back(U[i]); } queue<int> q; for(int i = 0; i < n; i++){ if(out[i] == 0){ forced[i] = 0; q.push(i); } } while(!q.empty()){ int x = q.front(); q.pop(); for(int node : radj[x]){ out[node]--; if(out[node] == 0 && forced[node] == 1) {q.push(node); forced[node] = 0;} if(A[node] == 1 && forced[node] == 1){ forced[node] = 0; q.push(node); } } } radj.assign(n, {}); out.assign(n, 0); for(int i = 0; i < m; i++){ if(forced[U[i]] == 1) continue; out[U[i]]++; radj[V[i]].push_back(U[i]); } for(int i = 0; i < n; i++){ if(out[i] == 0){ q.push(i); } } while(!q.empty()){ int x = q.front(); q.pop(); for(int node : radj[x]){ out[node]--; if(out[node] == 0 && forced[node] == 0) {q.push(node); forced[node] = 1;} if(A[node] == 0 && forced[node] == 0){ forced[node] = 1; q.push(node); } } } } vector<int> who_wins(vector<int> A, vector<int> R, vector<int> U, vector<int> V){ int n = (int)A.size(); int m = (int)U.size(); bool stop = 0; vector<bool> forced; //If 1, then it can be forced by B into a cycle with no R's. while(!stop){ stop = 1; forced.assign(n, 1); process(A, R, U, V, forced); for(int i = 0; i < n; i++){ if(forced[i] == 1 && R[i] == 1) {R[i] = 0; stop = 0;} } } vector<int> ans(n); for(int i = 0; i < n; i++){ if(forced[i] == 1) ans[i] = 0; else ans[i] = 1; } return ans; } //~ mt19937 gen(time(0)); //~ void generate(){ //~ for(int tt = 0; tt <= 10000; tt++){ //~ int n = gen() % 5 + 1; //~ int m = gen() % 5 + n; //~ vector<int> a(n), r(n), u(m), v(m); //~ for(int i = 0; i < n; i++) //~ a[i] = gen() % 2; //~ for(int i = 0; i < n; i++) //~ r[i] = gen() % 2; //~ for(int i = 0; i < n; i++){ //~ u[i] = i; //~ if(u[i] == n - 1) v[i] = u[i]; //~ else v[i] = u[i] + gen() % 2; //~ } //~ for(int i = n; i < m; i++){ //~ u[i] = gen() % n; //~ if(u[i] == n - 1) v[i] = u[i]; //~ else v[i] = u[i] + gen() % 2; //~ } //~ vector<int> res = who_wins(a, r, u, v); //~ vector<int> res2 = who_wins2(a, r, u, v); //~ if(res != res2){ //~ cout << n << " " << m << endl; //~ for(int x : a) cout << x << " "; //~ cout << endl; //~ for(int x : r) cout << x << " "; cout << endl; //~ for(int i = 0; i < m; i++){ //~ cout << u[i] << " " << v[i] << endl; //~ } //~ cout << "RES: "; //~ for(int x : res) cout << x << " "; cout << endl; //~ cout << "RES2: "; //~ for(int x : res2) cout << x << " "; cout << endl; //~ return; //~ } //~ } //~ } //~ int main() { //~ generate(); return 0; //~ freopen("in.txt", "r", stdin); //~ int n, m; //~ assert(2 == scanf("%d %d", &n, &m)); //~ vector<int> a(n), r(n), u(m), v(m); //~ for(int i = 0; i < n; i++) //~ assert(1 == scanf("%d", &a[i])); //~ for(int i = 0; i < n; i++) //~ assert(1 == scanf("%d", &r[i])); //~ for(int i = 0; i < m; i++) //~ assert(2 == scanf("%d %d", &u[i], &v[i])); //~ vector<int> res = who_wins(a, r, u, v); //~ for(int i = 0; i < (int)res.size(); i++) //~ printf(i ? " %d" : "%d", res[i]); //~ printf("\n"); //~ return 0; //~ }

Compilation message (stderr)

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:96:6: warning: unused variable 'm' [-Wunused-variable]
   96 |  int m = (int)U.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...