#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
const int Nmax=510, Kmax=Nmax*Nmax/2;
int N, M, p, par[Nmax], parc[Nmax], dep[Nmax], dfsn[Nmax], top[Nmax], low[Nmax], back[Nmax];
int total, chk[Kmax];
vector<pair<int, int>> adj[Nmax], adj2[Nmax];
vector<tuple<int, int, int>> tree;
vector<int> V;
int value(int x, int y) {
// cout<<"value "<<"delete "<<x<<", add "<<y<<"\n";
for(int &i:V) if(i==x) i=y;
int ret=count_common_roads(V);
for(int &i:V) if(i==y) i=x;
return ret;
}
void DFS(int curr, int prev) {
dfsn[curr]=top[curr]=++p;
for(auto [next, c]:adj[curr]) if(next!=prev) {
if(dfsn[next]) {
if(top[curr]>dfsn[next]) top[curr]=dfsn[next], back[curr]=c, low[curr]=curr;
}
else {
par[next]=curr, parc[next]=c, dep[next]=dep[curr]+1;
tree.push_back({curr, next, c});
adj2[curr].push_back({next, c});
DFS(next, curr);
if(top[curr]>top[next]) top[curr]=top[next], back[curr]=back[next], low[curr]=low[next];
}
}
}
void DFS2(int curr) {
for(auto [next, c]:adj2[curr]) {
DFS2(next);
if(chk[c]!=-1) continue;
// cout<<curr<<" -> "<<next<<"\n";
if(top[next]>dfsn[curr]) chk[c]=1;
else {
vector<int> tmp;
bool flag=false; int q=0;
for(int i=low[next]; dfsn[i]!=top[next]; i=par[i]) {
tmp.push_back(parc[i]);
if(chk[parc[i]]!=-1) flag=true, q=parc[i];
}
/*cout<<"tmp "<<curr<<", "<<next<<": ";
for(int i:tmp) cout<<i<<" ";
cout<<"\n";
cout<<flag<<", "<<back[next]<<"\n";*/
if(flag) {
chk[back[next]]=chk[q]+value(q, back[next])-total;
for(int i:tmp) if(chk[i]==-1) chk[i]=chk[back[next]]-value(i, back[next])+total;
}
else {
int X=total;
vector<int> Y;
for(int i:tmp) Y.push_back(value(i, back[next]));//, cout<<i<<" Y : "<<Y.back()<<"\n";
bool flag2=false;
for(int i=0; i<Y.size(); i++) {
if(Y[i]==X+1) flag2=true, chk[back[next]]=1, chk[tmp[i]]=0;
else if(Y[i]==X-1) flag2=true, chk[back[next]]=0, chk[tmp[i]]=1;
}
if(flag2) {
for(int i=0; i<Y.size(); i++) if(Y[i]==X) chk[tmp[i]]=chk[back[next]];
}
else {
chk[back[next]]=false;
for(int i=0; i<Y.size(); i++) if(Y[i]==X) chk[tmp[i]]=false;
}
}
}
}
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
N=n, M=u.size();
for(int i=0; i<M; i++) {
adj[u[i]].push_back({v[i], i}), adj[v[i]].push_back({u[i], i});
}
for(int i=0; i<M; i++) chk[i]=-1;
DFS(0, -1);
for(auto [u, v, c]:tree) V.push_back(c);
total=count_common_roads(V);
DFS2(0);
/*cout<<"tree:\n";
for(auto [u, v, c]:tree) cout<<u<<", "<<v<<": "<<c<<", "<<chk[c]<<"\n";
cout<<"\n";*/
for(int i=0; i<M; i++) if(chk[i]==-1) {
// cout<<"check "<<i<<"\n";
if(dep[u[i]]<dep[v[i]]) swap(u[i], v[i]);
chk[i]=chk[parc[u[i]]]+value(parc[u[i]], i)-total;
}
vector<int> ret;
for(int i=0; i<M; i++) if(chk[i]) ret.push_back(i);
/*cout<<"ret: ";
for(int i:ret) cout<<i<<" ";
cout<<"\n";*/
return ret;
}
Compilation message
simurgh.cpp: In function 'void DFS2(int)':
simurgh.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i=0; i<Y.size(); i++) {
| ~^~~~~~~~~
simurgh.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i=0; i<Y.size(); i++) if(Y[i]==X) chk[tmp[i]]=chk[back[next]];
| ~^~~~~~~~~
simurgh.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i=0; i<Y.size(); i++) if(Y[i]==X) chk[tmp[i]]=false;
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
604 KB |
correct |
2 |
Correct |
0 ms |
348 KB |
correct |
3 |
Correct |
0 ms |
348 KB |
correct |
4 |
Correct |
0 ms |
348 KB |
correct |
5 |
Correct |
0 ms |
348 KB |
correct |
6 |
Correct |
0 ms |
472 KB |
correct |
7 |
Correct |
1 ms |
348 KB |
correct |
8 |
Correct |
0 ms |
348 KB |
correct |
9 |
Correct |
0 ms |
348 KB |
correct |
10 |
Correct |
1 ms |
348 KB |
correct |
11 |
Correct |
1 ms |
348 KB |
correct |
12 |
Correct |
0 ms |
344 KB |
correct |
13 |
Correct |
1 ms |
348 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
604 KB |
correct |
2 |
Correct |
0 ms |
348 KB |
correct |
3 |
Correct |
0 ms |
348 KB |
correct |
4 |
Correct |
0 ms |
348 KB |
correct |
5 |
Correct |
0 ms |
348 KB |
correct |
6 |
Correct |
0 ms |
472 KB |
correct |
7 |
Correct |
1 ms |
348 KB |
correct |
8 |
Correct |
0 ms |
348 KB |
correct |
9 |
Correct |
0 ms |
348 KB |
correct |
10 |
Correct |
1 ms |
348 KB |
correct |
11 |
Correct |
1 ms |
348 KB |
correct |
12 |
Correct |
0 ms |
344 KB |
correct |
13 |
Correct |
1 ms |
348 KB |
correct |
14 |
Correct |
1 ms |
348 KB |
correct |
15 |
Correct |
1 ms |
348 KB |
correct |
16 |
Correct |
1 ms |
348 KB |
correct |
17 |
Correct |
1 ms |
348 KB |
correct |
18 |
Correct |
1 ms |
348 KB |
correct |
19 |
Correct |
1 ms |
348 KB |
correct |
20 |
Correct |
1 ms |
348 KB |
correct |
21 |
Correct |
1 ms |
552 KB |
correct |
22 |
Correct |
1 ms |
348 KB |
correct |
23 |
Correct |
1 ms |
472 KB |
correct |
24 |
Correct |
1 ms |
344 KB |
correct |
25 |
Correct |
0 ms |
348 KB |
correct |
26 |
Correct |
1 ms |
348 KB |
correct |
27 |
Correct |
1 ms |
348 KB |
correct |
28 |
Correct |
1 ms |
348 KB |
correct |
29 |
Correct |
1 ms |
348 KB |
correct |
30 |
Correct |
1 ms |
348 KB |
correct |
31 |
Correct |
1 ms |
476 KB |
correct |
32 |
Correct |
1 ms |
348 KB |
correct |
33 |
Correct |
1 ms |
344 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
604 KB |
correct |
2 |
Correct |
0 ms |
348 KB |
correct |
3 |
Correct |
0 ms |
348 KB |
correct |
4 |
Correct |
0 ms |
348 KB |
correct |
5 |
Correct |
0 ms |
348 KB |
correct |
6 |
Correct |
0 ms |
472 KB |
correct |
7 |
Correct |
1 ms |
348 KB |
correct |
8 |
Correct |
0 ms |
348 KB |
correct |
9 |
Correct |
0 ms |
348 KB |
correct |
10 |
Correct |
1 ms |
348 KB |
correct |
11 |
Correct |
1 ms |
348 KB |
correct |
12 |
Correct |
0 ms |
344 KB |
correct |
13 |
Correct |
1 ms |
348 KB |
correct |
14 |
Correct |
1 ms |
348 KB |
correct |
15 |
Correct |
1 ms |
348 KB |
correct |
16 |
Correct |
1 ms |
348 KB |
correct |
17 |
Correct |
1 ms |
348 KB |
correct |
18 |
Correct |
1 ms |
348 KB |
correct |
19 |
Correct |
1 ms |
348 KB |
correct |
20 |
Correct |
1 ms |
348 KB |
correct |
21 |
Correct |
1 ms |
552 KB |
correct |
22 |
Correct |
1 ms |
348 KB |
correct |
23 |
Correct |
1 ms |
472 KB |
correct |
24 |
Correct |
1 ms |
344 KB |
correct |
25 |
Correct |
0 ms |
348 KB |
correct |
26 |
Correct |
1 ms |
348 KB |
correct |
27 |
Correct |
1 ms |
348 KB |
correct |
28 |
Correct |
1 ms |
348 KB |
correct |
29 |
Correct |
1 ms |
348 KB |
correct |
30 |
Correct |
1 ms |
348 KB |
correct |
31 |
Correct |
1 ms |
476 KB |
correct |
32 |
Correct |
1 ms |
348 KB |
correct |
33 |
Correct |
1 ms |
344 KB |
correct |
34 |
Correct |
75 ms |
1628 KB |
correct |
35 |
Correct |
76 ms |
1812 KB |
correct |
36 |
Correct |
51 ms |
1372 KB |
correct |
37 |
Correct |
4 ms |
348 KB |
correct |
38 |
Correct |
74 ms |
1844 KB |
correct |
39 |
Correct |
64 ms |
1740 KB |
correct |
40 |
Correct |
49 ms |
1372 KB |
correct |
41 |
Correct |
76 ms |
1628 KB |
correct |
42 |
Correct |
78 ms |
1836 KB |
correct |
43 |
Correct |
40 ms |
1368 KB |
correct |
44 |
Correct |
33 ms |
1116 KB |
correct |
45 |
Correct |
38 ms |
1112 KB |
correct |
46 |
Correct |
32 ms |
860 KB |
correct |
47 |
Correct |
14 ms |
600 KB |
correct |
48 |
Correct |
1 ms |
344 KB |
correct |
49 |
Correct |
4 ms |
348 KB |
correct |
50 |
Correct |
13 ms |
780 KB |
correct |
51 |
Correct |
38 ms |
1116 KB |
correct |
52 |
Correct |
33 ms |
1112 KB |
correct |
53 |
Correct |
28 ms |
860 KB |
correct |
54 |
Correct |
40 ms |
1372 KB |
correct |
55 |
Correct |
38 ms |
1112 KB |
correct |
56 |
Correct |
38 ms |
1116 KB |
correct |
57 |
Correct |
39 ms |
1212 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
correct |
2 |
Correct |
0 ms |
348 KB |
correct |
3 |
Incorrect |
63 ms |
4524 KB |
WA in grader: NO |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
604 KB |
correct |
2 |
Correct |
0 ms |
348 KB |
correct |
3 |
Correct |
0 ms |
348 KB |
correct |
4 |
Correct |
0 ms |
348 KB |
correct |
5 |
Correct |
0 ms |
348 KB |
correct |
6 |
Correct |
0 ms |
472 KB |
correct |
7 |
Correct |
1 ms |
348 KB |
correct |
8 |
Correct |
0 ms |
348 KB |
correct |
9 |
Correct |
0 ms |
348 KB |
correct |
10 |
Correct |
1 ms |
348 KB |
correct |
11 |
Correct |
1 ms |
348 KB |
correct |
12 |
Correct |
0 ms |
344 KB |
correct |
13 |
Correct |
1 ms |
348 KB |
correct |
14 |
Correct |
1 ms |
348 KB |
correct |
15 |
Correct |
1 ms |
348 KB |
correct |
16 |
Correct |
1 ms |
348 KB |
correct |
17 |
Correct |
1 ms |
348 KB |
correct |
18 |
Correct |
1 ms |
348 KB |
correct |
19 |
Correct |
1 ms |
348 KB |
correct |
20 |
Correct |
1 ms |
348 KB |
correct |
21 |
Correct |
1 ms |
552 KB |
correct |
22 |
Correct |
1 ms |
348 KB |
correct |
23 |
Correct |
1 ms |
472 KB |
correct |
24 |
Correct |
1 ms |
344 KB |
correct |
25 |
Correct |
0 ms |
348 KB |
correct |
26 |
Correct |
1 ms |
348 KB |
correct |
27 |
Correct |
1 ms |
348 KB |
correct |
28 |
Correct |
1 ms |
348 KB |
correct |
29 |
Correct |
1 ms |
348 KB |
correct |
30 |
Correct |
1 ms |
348 KB |
correct |
31 |
Correct |
1 ms |
476 KB |
correct |
32 |
Correct |
1 ms |
348 KB |
correct |
33 |
Correct |
1 ms |
344 KB |
correct |
34 |
Correct |
75 ms |
1628 KB |
correct |
35 |
Correct |
76 ms |
1812 KB |
correct |
36 |
Correct |
51 ms |
1372 KB |
correct |
37 |
Correct |
4 ms |
348 KB |
correct |
38 |
Correct |
74 ms |
1844 KB |
correct |
39 |
Correct |
64 ms |
1740 KB |
correct |
40 |
Correct |
49 ms |
1372 KB |
correct |
41 |
Correct |
76 ms |
1628 KB |
correct |
42 |
Correct |
78 ms |
1836 KB |
correct |
43 |
Correct |
40 ms |
1368 KB |
correct |
44 |
Correct |
33 ms |
1116 KB |
correct |
45 |
Correct |
38 ms |
1112 KB |
correct |
46 |
Correct |
32 ms |
860 KB |
correct |
47 |
Correct |
14 ms |
600 KB |
correct |
48 |
Correct |
1 ms |
344 KB |
correct |
49 |
Correct |
4 ms |
348 KB |
correct |
50 |
Correct |
13 ms |
780 KB |
correct |
51 |
Correct |
38 ms |
1116 KB |
correct |
52 |
Correct |
33 ms |
1112 KB |
correct |
53 |
Correct |
28 ms |
860 KB |
correct |
54 |
Correct |
40 ms |
1372 KB |
correct |
55 |
Correct |
38 ms |
1112 KB |
correct |
56 |
Correct |
38 ms |
1116 KB |
correct |
57 |
Correct |
39 ms |
1212 KB |
correct |
58 |
Correct |
0 ms |
344 KB |
correct |
59 |
Correct |
0 ms |
348 KB |
correct |
60 |
Incorrect |
63 ms |
4524 KB |
WA in grader: NO |
61 |
Halted |
0 ms |
0 KB |
- |