Submission #713544

#TimeUsernameProblemLanguageResultExecution timeMemory
713544MohamedFaresNebiliToy Train (IOI17_train)C++14
0 / 100
2080 ms262144 KiB
#include <bits/stdc++.h> using namespace std; int N, M, P[5001]; int timer, tin[5001], low[5001]; vector<int> adj[5001], G[5001], S; bool vis[5001], self[5001], Scc[5001], ST[5001]; int station, reach[5001], DP[5001][5001]; int findSet(int v) { if(P[v] == v) return v; return P[v] = findSet(P[v]); } bool sameSet(int u, int v) { return findSet(u) == findSet(v); } void unionSet(int u, int v) { u = findSet(u), v = findSet(v); if(u == v) return; P[u] = v; } void dfs(int v) { tin[v] = low[v] = timer++; vis[v] = 1; S.push_back(v); for(auto u : adj[v]) { if(tin[u] == -1) dfs(u); if(vis[u]) low[v] = min(low[v], low[u]); } if(tin[v] == low[v]) { vector<int> V; while(1) { int U = S.back(); S.pop_back(); vis[U] = 0; V.push_back(U); if(U == v) break; } if(V.size() == 1) return; for(int l = 1; l < V.size(); l++) { unionSet(V[l], V[l - 1]); } } } int solve(int v, int t, int c, vector<int> A) { if(!reach[v]) return DP[v][t] = 0; if(DP[v][t] != -1) return DP[v][t]; if(ST[v]) t = N; if(DP[v][t] != -1) return DP[v][t]; if(v == station) c++; if(c == 2) return DP[v][t] = 1; if(t == 0) return DP[v][t] = 0; if(A[v] == 1) { if(self[v] && ST[v]) return DP[v][t] = 1; for(auto u : adj[v]) { if(solve(u, t - 1, c, A)) return DP[v][t] = 1; } return DP[v][t] = 0; } if(A[v] == 0) { if(self[v] && !ST[v]) return DP[v][t] = 0; for(auto u : adj[v]) { if(solve(u, t - 1, c, A) == 0) return DP[v][t] = 0; } return DP[v][t] = 1; } } vector<int> who_wins(vector<int> A, vector<int> R, vector<int> U, vector<int> V) { N = A.size(), M = U.size(); for(int l = 0; l < N; l++) { ST[l] = R[l], P[l] = l; station = (ST[l] == 1 ? l : station); } for(int l = 0; l < M; l++) { int X = U[l], Y = V[l]; if(X == Y) { self[X] = 1; if(ST[X] == 0) Scc[X] = 1; continue; } adj[X].push_back(Y); G[Y].push_back(X); } memset(tin, -1, sizeof tin); memset(DP, -1, sizeof DP); for(int l = 0; l < N; l++) { if(tin[l] != -1) continue; dfs(l); } queue<pair<int, int>> q; vector<int> D(N, 1e9 + 7); q.push({station, 0}); D[station] = 0; while(!q.empty()) { int X = q.front().first; q.pop(); reach[X] = 1; for(auto Y : G[X]) { if(D[X] + 1 < D[Y]) { D[Y] = D[X] + 1; q.push({Y, D[Y]}); } } } vector<int> res(N); for(int l = 0; l < N; l++) res[l] = solve(l, N, 0, A); return res; }

Compilation message (stderr)

train.cpp: In function 'void dfs(int)':
train.cpp:39:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |                 for(int l = 1; l < V.size(); l++) {
      |                                ~~^~~~~~~~~~
train.cpp: In function 'int solve(int, int, int, std::vector<int>)':
train.cpp:70:9: warning: control reaches end of non-void function [-Wreturn-type]
   70 |         }
      |         ^
#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...