이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include"train.h"
#include<cassert>
#include<numeric>
#include<queue>
#include<algorithm>
using namespace std;
struct dsu {
vector<int> p;
dsu(int n) : p(n, -1) {}
int find(int i) { return p[i] < 0 ? i : (p[i] = find(p[i])); }
int unite(int i, int j) { if (find(i) == find(j)) return 0; p[find(i)] = find(j); return 1; }
};
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
int n = a.size();
int m = u.size();
int is_subtask_1 = 1;
int is_subtask_3 = *min_element(a.begin(), a.end()) == 1;
int is_subtask_4 = *max_element(a.begin(), a.end()) == 0;
int is_subtask_5 = accumulate(r.begin(),r.end(),0)==1;
for (int i = 0; i < m; ++i) is_subtask_1 &= (u[i] == v[i]) + (u[i] == v[i] - 1);
std::vector<int> res(n);
if (is_subtask_1) { std::vector<int> loop(n), go(n); for (int i = 0; i < m; ++i) if (u[i] == v[i]) loop[u[i]] = 1; else go[u[i]] = 1; if (r[n-1]) res[n-1] = 1; for (int i = n - 2; i >= 0; --i) if (a[i]) { if (loop[i]) { if (r[i]) res[i] = 1; else { if (go[i]) res[i] = res[i + 1]; else res[i] = 0; } } else res[i] = res[i + 1]; } else { if (loop[i]) { if (r[i]) { if (go[i]) res[i] = res[i + 1]; else res[i] = 1; } else res[i] = 0; } else res[i] = res[i + 1]; } } else if (is_subtask_3) { vector<vector<int> > g(n); vector<int>loop(n); for(int i=0;i<m;++i){g[u[i]].push_back(v[i]); if(u[i]==v[i])loop[u[i]]=1; } vector<vector<int> > dp(n, vector<int>(n, 1e9)); for(int i=0;i<n;++i){ queue<int>q; dp[i][i]=0; q.push(i);while(q.size()){ auto u=q.front();q.pop();for(auto v:g[u])if(dp[i][v]==1e9)q.push(v),dp[i][v]=dp[i][u]+1; } } vector<int>good; for(int i=0;i<n;++i){ if(r[i]==0)continue; if(loop[i])good.push_back(i); else{ for(int j=0;j<n;++j){ if(j!=i&&dp[j][i]<1e9&&dp[i][j]<1e9){ good.push_back(i); break; } } } } for(int i=0;i<n;++i){ for(auto x:good)if(dp[i][x]<1e9){res[i]=1;break;} } return res; } else if (is_subtask_4) { vector<vector<int> > g(n); vector<int>loop(n); for(int i=0;i<m;++i){g[u[i]].push_back(v[i]); if(u[i]==v[i])loop[u[i]]=1; } vector<vector<int> > dp(n, vector<int>(n, 1e9)); for(int i=0;i<n;++i){ deque<int>q; dp[i][i]=0; q.push_front(i);while(q.size()){ auto u=q.front();q.pop_front(); for(auto v:g[u]){ int weght=r[v]; if(dp[i][v]>dp[i][u]+weght){ if(weght)q.push_back(v); else q.push_front(v); dp[i][v]=dp[i][u]+weght; } } } } vector<int>good; for(int i=0;i<n;++i){ if(r[i]==1)continue; if(loop[i])good.push_back(i); else{ for(int j=0;j<n;++j){ if(j!=i&&dp[j][i]==0&&dp[i][j]==0){ good.push_back(i); break; } } } } fill(res.begin(),res.end(),1); for(int i=0;i<n;++i) for(auto x:good)if(dp[i][x]<1e9){res[i]=0;break;} return res;
} else if (is_subtask_5) {
vector<vector<int> > rg(n),g(n); vector<int>loop(n); for(int i=0;i<m;++i){g[u[i]].push_back(v[i]); rg[v[i]].push_back(u[i]);if(u[i]==v[i])loop[u[i]]=1; }
vector<vector<int> > dp(n, vector<int>(n, 1e9)); for(int i=0;i<n;++i){ deque<int>q; dp[i][i]=0; q.push_front(i);while(q.size()){ auto u=q.front();q.pop_front(); for(auto v:g[u]){ int weght=r[v]; if(dp[i][v]>dp[i][u]+weght){ if(weght)q.push_back(v); else q.push_front(v); dp[i][v]=dp[i][u]+weght; } } } }
vector<int>go(n);
//dp = blahj's distance */
fill(go.begin(),go.end(),2);/*undecided*/
int x=max_element(r.begin(),r.end())-r.begin();
for(int i=0;i<n;++i){
if(i==x)continue;
if(dp[i][x]==1)go[i]=1;
if(a[i]==1){
}else{
if(loop[i])go[i]=0;
}
if(dp[i][x]==1e9) go[i]=0;
}
go[x]=1;
for(int i=0;i<=n;++i){
vector<int>unsure;
for(int j=0;j<n;++j)if(go[j]==2)unsure.push_back(j);
for(int u:unsure){
int c[3]={0};
for(int v:g[u]) ++c[go[v]];
if(a[u]){
if(c[1])go[u]=1;
else if(c[2]==0)go[u]=0;
}else{
if(c[0]+c[2]==0)go[u]=1;
else if(c[0])go[u]=0;
}
}
int cnt2=0;
for(int j=0;j<n;++j)cnt2+=go[j]==2;
if(cnt2==unsure.size())assert(0);
}
}
return res;
}
컴파일 시 표준 에러 (stderr) 메시지
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | if(cnt2==unsure.size())assert(0);
| ~~~~^~~~~~~~~~~~~~~
# | 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... |