| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1077085 |
2024-08-26T22:37:50 Z |
guanex |
Simurgh (IOI17_simurgh) |
C++14 |
|
69 ms |
4708 KB |
#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef long long ll;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef pair<long long, long long> pll;
typedef pair<char, int> ci;
typedef pair<string, int> si;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
#define pb push_back
#define fi first
#define se second
#define whole(v) v.begin(), v.end()
#define rwhole(v) v.rbegin(), v.rend()
#define inf INT_MAX/2
#define fro front
vi ans;
vector<vii> x(501);
ii fa[501];
int rs[125001];
int vis[501];
vi tree;
int z;
int cn = 0;
void df(int no, int f,int ideje){
if(ideje != -1){
tree.pb(ideje);
}
fa[no] = ii(f, ideje);
vis[no] = 1;
for(auto e:x[no]){
if(vis[e.fi]){
continue;
}
df(e.fi, no, e.se);
}
}
void dfs(int no,int ideje){
vis[no] = 1;
//cout << "currently " << no << '\n';
for(auto e:x[no]){
if(e.se == ideje || vis[e.fi] == 2){
continue;
}
if(vis[e.fi] == 1){
//cout << ".."<< e.fi << endl;
int f = no;
while(f != e.fi){
int ff = f;
f = fa[f].fi;
if(rs[fa[ff].se] != -1){
vi tre = tree;
for(int i = 0; i < tre.size(); ++i){
if(tre[i] == fa[ff].se){
tre[i] = e.se;
}
}
//cout << f << " " << ff << " " << fa[ff].se << endl;
for(auto e:tre){
//cout << e << " ";
}
//cout << endl;
int g = count_common_roads(tre);
cn++;
assert ( cn < 29999 );
//cout << g << endl;
if(g == z){
rs[e.se] = rs[fa[ff].se];
}else if(g == z+1){
rs[e.se] = 1;
}else{
rs[e.se] = 0;
}
f = e.fi;
}
}
if(rs[e.se] == -1){
f = no;
vector < int > seen;
while(f != e.fi){
int ff = f;
f = fa[f].fi;
vi tre = tree;
//cout << f << " " << ff << " " << fa[ff].se << endl;
for(int i = 0; i < tre.size(); ++i){
if(tre[i] == fa[ff].se){
tre[i] = e.se;
}
}
for(auto e:tre){
//cout << e << " ";
}
//cout << endl;
int g = count_common_roads(tre);
cn++;
assert ( cn < 29999 );
//cout << g << endl;
if(g == z){
seen.push_back ( fa[ff].se );
continue;
}else if(g == z+1){
rs[e.se] = 1;
rs[fa[ff].se] = 0;
f = e.fi;
}else{
rs[e.se] = 0;
rs[fa[ff].se] = 1;
f = e.fi;
}
}
if ( rs[e.se] == -1 ) {
rs[e.se] = 0;
}
for (auto &hh : seen) rs[hh] = 0;
}
f = no;
while(f != e.fi){
int ff = f;
f = fa[f].fi;
if(rs[fa[ff].se] != -1){
continue;
}
vi tre = tree;
for(int i = 0; i < tre.size(); ++i){
if(tre[i] == fa[ff].se){
tre[i] = e.se;
}
}
//cout << f << " " << ff << " " << fa[ff].se << endl;
for(auto e:tre){
//cout << e << " ";
}
//cout << endl;
int g = count_common_roads(tre);
cn++;
assert ( cn < 29999 );
//cout << g << endl;
if(g == z){
rs[fa[ff].se] = rs[e.se];
}else if(g == z+1){
rs[e.se] = 1;
rs[fa[ff].se] = 0;
f = e.fi;
}else{
rs[e.se] = 0;
rs[fa[ff].se] = 1;
f = e.fi;
}
}
//cout << endl << endl;
continue;
}
dfs(e.fi, e.se);
}
vis[no] = 2;
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
for(int i = 0; i < u.size(); ++i){
x[u[i]].pb(ii(v[i], i));
x[v[i]].pb(ii(u[i], i));
}
fa[0] = ii(0, -1);
df(0, 0, -1);
memset(vis, 0, sizeof vis);
memset(rs, -1, sizeof rs);
z = count_common_roads(tree);
if(z == n-1){
return tree;
}
dfs(0, -1);
////cout << 1 << endl;
for(auto e:tree){
if(rs[e] == -1){
rs[e] = 1;
}
}
for(int i = 0; i < 125001; ++i){
if(rs[i] == 1)
ans.pb(i);
}
assert(ans.size() <= n + 1);
for(auto e:ans){
//cout << e << endl;
}
return ans;
}
Compilation message
simurgh.cpp: In function 'void dfs(int, int)':
simurgh.cpp:62:38: 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 < tre.size(); ++i){
| ~~^~~~~~~~~~~~
simurgh.cpp:68:30: warning: unused variable 'e' [-Wunused-variable]
68 | for(auto e:tre){
| ^
simurgh.cpp:94:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(int i = 0; i < tre.size(); ++i){
| ~~^~~~~~~~~~~~
simurgh.cpp:99:30: warning: unused variable 'e' [-Wunused-variable]
99 | for(auto e:tre){
| ^
simurgh.cpp:134:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for(int i = 0; i < tre.size(); ++i){
| ~~^~~~~~~~~~~~
simurgh.cpp:140:26: warning: unused variable 'e' [-Wunused-variable]
140 | for(auto e:tre){
| ^
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:169:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
169 | for(int i = 0; i < u.size(); ++i){
| ~~^~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from simurgh.cpp:2:
simurgh.cpp:192:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
192 | assert(ans.size() <= n + 1);
| ~~~~~~~~~~~^~~~~~~~
simurgh.cpp:193:14: warning: unused variable 'e' [-Wunused-variable]
193 | for(auto e:ans){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
856 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
856 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
856 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
856 KB |
correct |
| 2 |
Correct |
1 ms |
860 KB |
correct |
| 3 |
Incorrect |
69 ms |
4708 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
856 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
