// moreflags=grader.cpp
// 11
#include "simurgh.h"
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>
#include<algorithm>
struct Dsu{
std::vector<int> data;
Dsu(int number){reset(number);}
void reset(int number){data.assign(number, -1);}
int root(int node){return data[node]>=0 ? data[node]=root(data[node]): node;}
bool join(int first, int sec){
first=root(first); sec=root(sec);
if(first==sec) return false;
data[first]=sec;
return true;
}
};
struct Edge{int node, index;};
std::vector<std::vector<Edge>> add;
std::vector<int> par, depth, parIndex;
std::vector<char> visited;
void work(int node, int curPar, int curDepth){
par[node]=curPar; depth[node]=curDepth;
assert(not visited[node]); visited[node]=true;
for(auto [child, index]: add[node]) if(not visited[child]){
parIndex[child]=index;
work(child, node, curDepth+1);
}
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
// construct a DFS tree
add.resize(n);
for(int index=0; index<(int)u.size(); ++index){
auto const first=u[index], sec=v[index];
add[first].push_back({sec, index});
add[sec].push_back({first, index});
}
par.resize(n); depth.resize(n);
visited.assign(n, false);
parIndex.resize(n); parIndex[0]=-1;
work(0, -1, 0);
// compute value of that tree
std::vector<int> tmp; tmp.reserve(n-1);
for(int node=0; node<n; ++node)
for(auto [other, index]: add[node]) if(depth[other]==depth[node]-1)
tmp.push_back(index);
int const treeValue=count_common_roads(tmp);
// compute individual edges' values
std::vector<int> value(u.size(), -1);
for(int node=0; node<n; ++node){
for(auto [other, backIndex]: add[node]) if(depth[other]<depth[node]-1){
// back edge
int& backValue=value[backIndex];
assert(backValue==-1);
/*
for(int x=node; x!=other; x=par[x]){
if(value[parIndex[x]]<0) goto anyUndefined;
}
continue;
*/
anyUndefined:
bool guessBackValue=true;
backValue=0; // this is the guess.
for(int x=node; x!=other; x=par[x]){
int& curValue=value[parIndex[x]];
if(guessBackValue or curValue<0){
auto const iterator=std::find(begin(tmp), end(tmp), parIndex[x]);
*iterator=backIndex;
auto const v=count_common_roads(tmp)-treeValue; // == backValue-curValue
*iterator=parIndex[x];
switch(v){
case 0:
{
if(curValue>=0){
if(guessBackValue){
assert(backValue==0); backValue=curValue;
guessBackValue=false;
}else{
assert(curValue==backValue);
}
}else{
curValue=backValue;
}
break;
}
case -1:
{
assert(curValue!=0); curValue=1;
assert(backValue==0);
if(guessBackValue){
guessBackValue=false; // already guessed correctly
}
break;
}
case 1:
{
assert(v==1);
assert(curValue!=1);
if(guessBackValue){ // guessed incorrectly, must fix values
assert(backValue==0);
backValue=1;
for(int y=node; y!=x; y=par[y]){
assert(value[y]==0); value[y]=1;
}
}else assert(backValue==1);
curValue=0; backValue=1; guessBackValue=false;
break;
}
default:
assert(false); __builtin_unreachable();
}
}
}
if(guessBackValue){
assert(backValue==0);
for(int x=node; x!=other; x=par[x])
assert(value[parIndex[x]]==0);
// also guessed correctly (there's no way the values of all those edges can be 1 at the same time)
}
}
}
// double check that tmp is the DFS tree
for(int node=0; node<n; ++node)
for(auto [other, index]: add[node]) if(depth[other]==depth[node]-1){
assert(std::find(begin(tmp), end(tmp), index)!=tmp.end());
}
for(auto index: tmp)
if(value[index]==-1) value[index]=1; // a bridge
tmp.clear();
for(int index=0; index<(int)value.size(); ++index){
assert(value[index]>=0);
if(value[index]) tmp.push_back(index);
}
return tmp;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:72:1: warning: label 'anyUndefined' defined but not used [-Wunused-label]
72 | anyUndefined:
| ^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
correct |
| 2 |
Incorrect |
0 ms |
256 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
correct |
| 2 |
Incorrect |
0 ms |
256 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
correct |
| 2 |
Incorrect |
0 ms |
256 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
correct |
| 2 |
Incorrect |
1 ms |
256 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
correct |
| 2 |
Incorrect |
0 ms |
256 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
