| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 282487 | MohamedAhmed04 | 장난감 기차 (IOI17_train) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "train.h"
#include "grader.cpp"
using namespace std ;
const int MAX = 5010 ;
int A[MAX] , R[MAX] , vis[MAX] , vis2[MAX] ;
vector< vector<int> >adj(MAX) ;
vector< vector<int> >adj2(MAX) ;
vector< vector<int> >sccadj(MAX) ;
int n , m ;
vector<int>topo ;
int comb[MAX] ;
vector<int>combnodes[MAX] ;
int dp[MAX] ;
void dfs(int node)
{
vis[node] = 1 ;
for(auto &child : adj[node])
{
if(vis[child])
continue ;
dfs(child) ;
}
topo.push_back(node) ;
}
int id = 0 ;
void dfs2(int node)
{
vis2[node] = 1 ;
comb[node] = id ;
combnodes[id].push_back(node) ;
for(auto &child : adj2[node])
{
if(vis2[child])
continue ;
dfs2(child) ;
}
}
void dfs3(int node)
{
vis[node] = 1 ;
for(auto &child : sccadj[node])
{
if(vis[child])
continue ;
dfs3(child) ;
}
topo.push_back(node) ;
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
n = a.size() ;
m = u.size() ;
for(int i = 1 ; i <= n ; ++i)
A[i] = a[i-1] , R[i] = r[i-1] ;
for(int i = 0 ; i < m ; ++i)
{
adj[u[i]+1].push_back(v[i]+1) ;
adj2[v[i]+1].push_back(u[i]+1) ;
}
for(int i = 1 ; i <= n ; ++i)
{
if(vis[i])
continue ;
dfs(i) ;
}
reverse(topo.begin() , topo.end()) ;
for(auto &i : topo)
{
if(vis2[i])
continue ;
++id ;
dfs2(i) ;
}
for(int i = 1 ; i <= id ; ++i)
{
for(auto &node : combnodes[i])
{
for(auto &child : adj[node])
{
if(comb[child] != i)
sccadj[i].push_back(comb[child]) ;
}
}
}
topo.clear() ;
memset(vis , 0 , sizeof(vis)) ;
for(int i = 1 ; i <= id ; ++i)
{
if(vis[i])
continue ;
dfs3(i) ;
}
reverse(topo.begin() , topo.end()) ;
for(int i = topo.size()-1 ; i >= 0 ; --i)
{
int id = topo[i] ;
dp[id] = 0 ;
for(auto &node : combnodes[id])
dp[id] |= R[node] ;
for(auto &child : sccadj[id])
dp[id] |= dp[child] ;
}
vector<int>ans ;
for(int i = 1 ; i <= n ; ++i)
{
if(dp[comb[i]])
ans.push_back(1) ;
else
ans.push_back(0) ;
}
return ans ;
}