제출 #295928

#제출 시각아이디문제언어결과실행 시간메모리
295928Trickster장난감 기차 (IOI17_train)C++14
0 / 100
2088 ms262148 KiB
#include "train.h" #include <algorithm> #include <string.h> #include <iostream> #include <stdio.h> #include <vector> #include <queue> #include <cmath> #include <set> #include <map> using namespace std; #define N 5010 #define ff first #define ss second #define ll long long #define pb push_back #define mod 1000000007 #define pii pair <int, int> #define sz(a) int(a.size()) // #pragma GCC target ("avx2") // #pragma GCC optimization ("O3") // #pragma GCC optimization ("unroll-loops") ll bigmod(ll a,ll e) {if(e==0)return 1;ll x=bigmod(a*a%mod,e>>1);return e&1?x*a%mod:x;} int n, m; int Ch[N]; int vis[N]; int M[N][N]; vector <int> E[N], T[N], v, c; void dfs(int nd, int pr) { v.pb(nd); vis[nd] = vis[pr]+1; if(Ch[nd] == 1) c.pb(nd); for(auto i: E[nd]) { if(vis[i]) { int ok = 1; if(c.empty() || vis[c.back()] < vis[i]) ok = 0; v.pb(i); int sz = v.size(); for(int h = 0; h < sz-1; h++) { if(vis[v[h]] < vis[i]) continue; M[v[h]][v[h+1]] = max(ok, M[v[h]][v[h+1]]); } v.pop_back(); continue; } dfs(i, nd); } vis[nd] = 0; v.pop_back(); if(Ch[nd] == 1) c.pop_back(); } vector <int> who_wins(vector <int> a, vector <int> r, vector <int> u, vector <int> v) { n = sz(a), m = sz(u); for(int i = 0; i < n; i++) Ch[i] = r[i]; for(int i = 0; i < m; i++) E[u[i]].pb(v[i]), T[v[i]].pb(u[i]); for(int i = 0; i < n; i++) for(int h = 0; h < n; h++) M[i][h] = -1; dfs(0, -1); // for(int i = 0; i < m; i++) // cout << M[{u[i], v[i]}] << " "; int A[N]; queue <int> Q; memset(A, 0, sizeof(A)); memset(vis, 0, sizeof(vis)); for(int i = 0; i < n; i++) { int ok = -1, ok2 = -1; for(auto h: E[i]) { if(M[i][h] == 0) ok = 0; if(M[i][h] == 1) ok2 = 1; } if(ok != -1 || ok2 != -1) Q.push(i), vis[i] = 1; } while(!Q.empty()) { int nd = Q.front(); Q.pop(); int ok = -1, ok2 = -1; for(auto i: E[nd]) { if(M[nd][i] == 0) ok = 0; if(M[nd][i] == 1) ok2 = 1; } if(ok != -1 && ok2 == -1) A[nd] = 0; else if(ok == -1 && ok2 != -1) A[nd] = 1; else A[nd] = a[nd]; for(auto i: T[nd]) { if(vis[i] == 1) continue; M[i][nd] = A[nd]; Q.push(i); } } vector <int> ret; for(int i = 0; i < n; i++) ret.pb(A[i]); return ret; }
#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...