#include "simurgh.h"
#ifndef EVAL
#include "grader.cpp"
#endif // EVAL
#include <bits/stdc++.h>
using namespace std;
#define lol long long
#define pii pair<int,int>
#define OK puts("OK");
#define NO puts("NO");
#define YES puts("YES");
#define fr first
#define sc second
#define ret return
#define scanl(a) scanf("%lld",&a);
#define scanll(a,b) scanf("%lld %lld",&a, &b);
#define scanlll(a,b,c) scanf("%lld %lld %lld",&a,&b,&c);
#define scan1(a) scanf("%d",&a);
#define scan2(a,b) scanf("%d %d",&a, &b);
#define scan3(a,b,c) scanf("%d %d %d",&a,&b,&c);
#define all(s) s.begin(),s.end()
#define allr(s) s.rbegin(),s.rend()
#define pb push_back
#define sz(v) (int)v.size()
#define endi puts("");
#define eps 1e-12
vector <pii> g[501];
vector <int> which,cycle,top,otvet;
bool vis[501],can[1000001],used[1000001],pos[1000001];
int kto[501][501];
void dfs(int x){
vis[x] = 1;
for (pii to: g[x])
if (vis[to.fr] == 0){
which.pb(to.sc);
dfs(to.fr);
}
}
void find_cycle(int x,int pr = -1){
top.pb(x);
vis[x]=1;
for (pii to: g[x]){
if (to.fr != pr && can[to.sc] == 1){
if (vis[to.fr] == 1){
int pr = to.fr;
while (!top.empty()){
cycle.pb(kto[top.back()][pr]);
pr = top.back();
if (top.back() == to.fr)break;
top.pop_back();
}
ret;
}
if (!cycle.empty())ret;
if (vis[to.fr] == 0){
find_cycle(to.fr,x);
}
}
if (!cycle.empty())ret;
}
if (!cycle.empty())ret;
top.pop_back();
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
vector<int> bosh,a;
int i;
for (i=0;i<u.size();++i){
g[u[i]].pb({v[i],i});
g[v[i]].pb({u[i],i});
kto[u[i]][v[i]] = i;
kto[v[i]][u[i]] = i;
a.pb(0);
otvet.pb(-1);
}
dfs(0);
for (int x : which){
used[x] = 1;
can[x] = 1;
a[x] = 1;
otvet[x]=1;
}
for (i=0;i<u.size();++i)
if (!used[i])
bosh.pb(i);
for (int x: bosh){
for (i=0;i<n;++i)vis[i] = 0;
can[x] = 1;
a[x] = 1;
cycle.clear();
top.clear();
vector <pii> ans;
find_cycle(0);
for (int y: cycle){
if (pos[y] == 1)continue;
a[y]=0;
pos[y]=1;
vector <int> ask;
for (i=0;i<u.size();++i)
if (a[i] == 1)ask.pb(i);
if (ask.size() != n-1)assert(0);
ans.pb({count_common_roads(ask),y});
a[y]=1;
}
sort(all(ans));
if (ans.empty())continue;
int mn = ans.back().fr;
for (i=0;i<ans.size();++i){
if (mn > ans[i].fr){
otvet[ans[i].sc]=1;
}
else
otvet[ans[i].sc]=0;
}
can[x]=0;
a[x]=0;
}
vector <int> res;
for (i =0;i<otvet.size();++i){
if (otvet[i] == 1){
res.pb(i);
}
}
ret res;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:69:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (i=0;i<u.size();++i){
| ~^~~~~~~~~
simurgh.cpp:85:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for (i=0;i<u.size();++i)
| ~^~~~~~~~~
simurgh.cpp:101:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for (i=0;i<u.size();++i)
| ~^~~~~~~~~
simurgh.cpp:103:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
103 | if (ask.size() != n-1)assert(0);
| ~~~~~~~~~~~^~~~~~
simurgh.cpp:110:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for (i=0;i<ans.size();++i){
| ~^~~~~~~~~~~
simurgh.cpp:121:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for (i =0;i<otvet.size();++i){
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
correct |
| 2 |
Incorrect |
1 ms |
364 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
