| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 612505 | MohamedAliSaidane | 장난감 기차 (IOI17_train) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#include "train.h"
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
#define pb push_back
#define popb pop_back
#define all(x) (x).begin(),(x).end()
#define ff first
#define ss second
const int nax = 5004;
const int MOD = 1e9 + 7;
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v);
int n, m;
vi adj[nax];
int vis[nax];
int A[nax], C[nax], self[nax];
int dfs(int x, int dep = n)
{
vis[x] = 1;
dep = C[x] ? n: dep;
if(dep == 0)
return A[x] ? 0 : 1;
int rep = 0;
for(auto e: adj[x])
{
if(vis[e])
{
if(A[x])
rep = 1;
}
else
{
if(A[e] == A[x])
{
if(rep == 0 )
rep = dfs(e, dep - 1);
}
else
{
if(rep == 0)
rep = 1 - dfs(e, dep - 1);
}
}
}
vis[x] = 0;
return rep;
}
vi who_wins(vi a, vi r, vi u, vi v)
{
n = a.size();
m = u.size();
for(int i = 0 ; i < n; i++)
{
A[i] = a[i];
C[i ] = r[i];
}
for(int i = 0 ; i < m; i ++)
{
adj[u[i]].pb(v[i]);
if(u[i] == v[i])
self[i] = 1;
}
vi ans(n, 0);
for(int i = n - 1;i >= 0; i--)
{
if(a[i])
{
if(C[i] == 1 && self[i] == 1)
ans[i] = 1;
else
{
ans[i] = 0;
for(auto e: adj[i])
if(ans[e] == 1)
ans[i] = 1;
}
}
else
{
if(C[i] == 0 && self[i] == 1)
ans[i] = 0;
else
{
ans[i] = 1;
for(auto e: adj[i])
if(ans[e] == 0)
ans[i]= 0;
}
}
}
return ans;
}
int main() {
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;
}