Submission #593947

#TimeUsernameProblemLanguageResultExecution timeMemory
593947FatihSolakToy Train (IOI17_train)C++17
0 / 100
2079 ms24828 KiB
#include "train.h" #include <bits/stdc++.h> #define N 5005 using namespace std; long long dp[N]; long long ndp[N]; bool edge[N][N]; vector<int> adj[N]; vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) { int n = a.size(); int m = u.size(); for(int i = 0;i<m;i++){ edge[u[i]][v[i]] = 1; adj[u[i]].push_back(v[i]); } for(int i = 0;i<n;i++){ if(a[i] == 0 && r[i] == 0 && edge[i][i]){ dp[i] = -1e9; } if(r[i]) dp[i] = n; } cout << endl; for(int i=0;i<10*n;i++){ for(int j = 0;j<n;j++){ if(a[j]){ ndp[j] = -1e9; for(auto u:adj[j]){ ndp[j] = max(ndp[j],dp[u] + r[j]*n - 1); } ndp[j] = min(ndp[j],3ll*n); } else{ ndp[j] = 1e9; for(auto u:adj[j]){ ndp[j] = min(ndp[j],dp[u] + r[j]*n - 1); } ndp[j] = min(ndp[j],3ll*n); } } for(int j = 0;j<n;j++){ dp[j] = ndp[j]; //cout << dp[j] << " "; } //cout << endl; } vector<int> res(n); for(int i = 0; i < n; i++){ res[i] = (dp[i] >= -n); } return res; }
#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...