# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
65152 | mohammad_kilani | 장난감 기차 (IOI17_train) | C++17 | 116 ms | 1920 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "train.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
vector< int > res , a , r , g[N] , g2[N];
int n , out[N] , out2[N] , last , vis[N] , vi;
bool have[N];
void make(int node){
for(int i=0;i<g2[node].size();i++){
if(res[g2[node][i]] != -1)
continue;
out[g2[node][i]]--;
if(a[node] == a[g2[node][i]]){
if(res[node] == a[node]){
res[g2[node][i]] = a[node];
make(g2[node][i]);
}
else{
if(out[g2[node][i]] == 0){
res[g2[node][i]] = a[node] ^ 1;
make(g2[node][i]);
}
}
}
else{
if(res[node] != a[node]){
res[g2[node][i]] = a[node] ^ 1;
make(g2[node][i]);
}
else{
if(out[g2[node][i]] == 0){
res[g2[node][i]] = a[node];
make(g2[node][i]);
}
}
}
}
}
void make2(int node){
for(int i=0;i<g2[node].size();i++){
if(have[g2[node][i]]) continue;
out2[g2[node][i]]--;
if(out2[g2[node][i]] == 0){
have[g2[node][i]] = true;
make2(g2[node][i]);
continue;
}
if(a[g2[node][i]] == 1){
have[g2[node][i]] = true;
make2(g2[node][i]);
}
}
}
bool DFS(int node){
if(a[node] == 0)
return (res[node] == 1);
if(node == last)
return true;
vis[node] = vi;
for(int i=0;i<g[node].size();i++){
if(vis[g[node][i]] != vi && DFS(g[node][i]))
return true;
}
return false;
}
std::vector<int> who_wins(std::vector<int> A, std::vector<int> R, std::vector<int> u, std::vector<int> v) {
a = A;
n = (int)a.size();
r = R;
res.resize(n , -1);
for(int i = 0;i<(int)u.size();i++){
if(u[i] == v[i] && a[i] == 1 && r[i] == 0) continue;
g[u[i]].push_back(v[i]);
g2[v[i]].push_back(u[i]);
out[u[i]]++;
out2[u[i]]++;
}
for(int i=0;i<n;i++){
if(have[i]) continue;
have[i] = r[i];
if(have[i])
make2(i);
}
for(int i=0;i<n;i++){
if(res[i] != -1) continue;
if(!have[i]){
res[i] = 0;
make(i);
}
}
for(int i=0;i<n;i++){
if(res[i] == -1 && a[i] == 0){
res[i] = 1;
make(i);
}
}
for(int i=0;i<n;i++){
if(res[i] != -1) continue;
last = i;
vi++;
if(r[i]){
for(int j = 0;j<g[i].size();j++){
if(vis[g[i][j]] != vi && DFS(g[i][j])){
res[i] = 1;
break;
}
}
if(res[i] != -1)
make(i);
}
}
for(int i=0;i<n;i++){
if(res[i] == -1)
res[i] = 0;
}
return res;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |