이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
//#include "train.h"
vector<int> v[5002];
vector<int> rv[5002];
bool use[5002];
vector<int> bc;
inline void dfs(int b){
use[b]=true;
for(int go:v[b]){
if(use[go]==false){
dfs(go);
}
}
bc.push_back(b);
}
int belong[5002];
inline void dfs2(int b,int be){
use[b]=false;
belong[b]=be;
for(int go:rv[b]){
if(use[go]){
dfs2(go,be);
}
}
}
int m;
int n;
void scc(){
for(int i=0;i<n;i++){
if(use[i]==false){
dfs(i);
}
}
reverse(bc.begin(),bc.end());
for(int i=0;i<bc.size();i++){
if(use[bc[i]]){
dfs2(bc[i],m);
m++;
}
}
}
vector<int> ed[5002];
bool ok[5002];
int us[5002];
int u_s;
bool bor[5002];
bool are[5002];
vector<int> r;
inline bool a_walk(int node){
us[node]=u_s;
if(are[node])return true;
if(ok[belong[node]])return true;
//if(r[node])return true;
for(int go:v[node]){
if(us[go]!=u_s){
if(a_walk(go))return true;
}
}
return false;
}
std::vector<int> who_wins(std::vector<int> a1, std::vector<int> r1, std::vector<int> u1, std::vector<int> v1) {
r=r1;
n=a1.size();
for(int i=0;i<n;i++){
if(u1[i]==v1[i]){
if(r1[u1[i]]){
are[u1[i]]=true;
}
else{
bor[u1[i]]=true;
}
continue;
}
v[u1[i]].push_back(v1[i]);
rv[v1[i]].push_back(u1[i]);
}
scc();
for(int i=0;i<n;i++){
for(int go:v[i]){
if(belong[i]!=belong[go]){
ed[belong[i]].push_back(belong[go]);
}
}
}
for(int i=0;i<m;i++){
sort(ed[i].begin(),ed[i].end());
ed[i].erase(unique(ed[i].begin(),ed[i].end()),ed[i].end());
}
for(int i=0;i<n;i++){
ok[belong[i]]|=r1[i];
}
vector<int> ret(a1.size(),0);
for(int i=0;i<n;i++){
u_s++;
if(a_walk(i)){
ret[i]=1;
}
}
return ret;
}
컴파일 시 표준 에러 (stderr) 메시지
train.cpp: In function 'void scc()':
train.cpp:43:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<bc.size();i++){
~^~~~~~~~~~
# | 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... |