| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 427443 | TLP39 | 장난감 기차 (IOI17_train) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "train.h"
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> point_to[5003];
int ori_outdeg[5003]={};
int temp_outdeg[5003];
vector<int> res_graph[5003];
int graph_outdeg[5003]={};
void getreach(int v)
{
queue<int> q;
int tt;
for(int i=0;i<n;i++) temp_outdeg[i]=ori_outdeg[i];
for(int i=0;i<point_to[v].size();i++)
{
temp_outdeg[point_to[v][i]]--;
if(!temp_outdeg[point_to[v][i]]) q.push_back(point_to[v][i]);
}
while(!q.empty())
{
tt=q.front();
q.pop();
res_graph[v].push_back(tt);
graph_outdeg[tt]++;
if(tt==v) continue;
for(int i=0;i<point_to[tt].size();i++)
{
temp_outdeg[point_to[tt][i]]--;
if(!temp_outdeg[point_to[tt][i]]) q.push_back(point_to[tt][i]);
}
}
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
std::vector<int> res(a.size(),1);
n=a.size();
m=u.size();
for(int i=0;i<m;i++)
{
point_to[v[i]].push_back(u[i]);
ori_outdeg[u[i]]++;
}
for(int i=0;i<n;i++) if(a[i]) ori_outdeg[i]=1;
for(int i=0;i<n;i++)
{
if(r[i]) getreach(i);
}
queue<int> q;
for(int i=0;i<n;i++) if(!graph_outdeg[i]) q.push(i);
int fr;
while(!q.empty())
{
fr=q.front();
q.pop();
res[fr]=0;
for(int i=0;i<res_graph[fr].size();i++)
{
graph_outdeg[res_graph[fr][i]]--;
if(!graph_outdeg[res_graph[fr][i]]) q.push(res_graph[fr][i]);
}
}
return res;
}