| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1198650 | dosts | 장난감 기차 (IOI17_train) | C++20 | 0 ms | 0 KiB |
#include "train.h"
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
using namespace std;
vi ans,go,chk;
vector<vi> edges,egdes;
void dfs(int node) {
for (auto it : egdes[node]) {
if (ans[it]) continue;
ans[it] = 1;
dfs(it);
}
}
int fl;
vi rr;
void dfs2(int node) {
for (auto it : edges[node]) {
if (rr[it]) continue;
if (go[it]) continue;
go[it] = 1;
dfs2(it);
}
}
std::vector<int32_t> who_wins(std::vector<int32_t> a, std::vector<int32_t> r, std::vector<int32_t> u, std::vector<int32_t> v) {
int n = a.size();
rr = r;
std::vector<int32_t> res(n,1);
ans.assign(n,0);
go.assign(n,0);
edges.resize(n);
egdes.resize(n);
int m = u.size();
for (int i = 0;i<m;i++) {
edges[u[i]].push_back(v[i]);
egdes[v[i]].push_back(u[i]);
}
for (int i = 0;i<n;i++) {
if (r[i]) continue;
go.assign(n,0);
dfs2(i);
if (!go[i]) continue;
dfs(i);
for (int i = 0;i<n;i++) if (ans[i]) res[i] = 0;
}
return res;
}