| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 60990 |
2018-07-25T05:21:10 Z |
tugushka |
Simurgh (IOI17_simurgh) |
C++14 |
|
3000 ms |
1049600 KB |
#include "simurgh.h"
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef pair < int, int > pii;
map < pii, int > id, gold;
vector < int > cyc, exc;
int nn, mm, p[505], d[505], cyc_len;
bool v[505][505];
void find_cycle(){
cyc.clear();
memset( p, -1, sizeof(p) );
memset( d, -1, sizeof(d) );
queue < int > q;
q.push(0);
d[0] = 0;
int dep = 0, t1 = -1, t2, c;
while( !q.empty() ){
int sz = q.size();
dep++;
while(sz--){
int u = q.front();
// cout << u << ' ' << d[u] << ' ' << p[u] << endl;
q.pop();
for(int it = 0 ; it < nn ; it++){
if( !v[u][it] ) continue;
if( p[u] == it ) continue;
// cout << u << " --> " << *it << endl;
if( d[it] == -1 ){
p[it] = u;
d[it] = dep;
q.push(it);
}
else{
t1 = it;
t2 = u;
// cout << "Tails : " << t1 << ' ' << t2 << endl;
break;
}
}
if( t1 != -1 ) break;
}
if( t1 != -1 ) break;
}
vector < int > cw, ccw;
while( t1 != t2 ){
if( d[t1] < d[t2] ) ccw.pb(t2), t2 = p[t2];
else if( d[t1] > d[t2] ) cw.pb(t1), t1 = p[t1];
else ccw.pb(t2), cw.pb(t1), t2 = p[t2], t1 = p[t1];
}
cyc.pb(t1);
for(int i = ccw.size()-1 ; i >= 0 ; i--) cyc.pb(ccw[i]);
for(int i = 0 ; i < cw.size() ; i++) cyc.pb(cw[i]);
cyc_len = cyc.size();
cyc.pb(t1);
/*
cout << "Found\n";
for(int i = 0 ; i < cyc.size() ; i++) cout << cyc[i] << ' ';
cout << endl;
*/
}
void eval(){
exc.clear();
memset(p, -1, sizeof(p));
queue < int > q;
for(int i = 0 ; i < cyc.size() ; i++) q.push(cyc[i]), p[cyc[i]] = cyc[i];
while( !q.empty() ){
int u = q.front();
q.pop();
for( int it = 0 ; it < nn ; it++ ){
if( !v[u][it] ) continue;
if( p[it] == -1 ){
p[it] = u;
// cout << "Excess : " << u << ' ' << *it << endl;
exc.pb( id[ mp(u, it) ] );
q.push(it);
}
}
}
}
vector<int> find_roads(int _n, vector<int> _u, vector<int> _v) {
nn = _n;
mm = _u.size();
for(int i = 0 ; i < mm ; i++){
v[_u[i]][_v[i]] = v[_v[i]][_u[i]] = 1;
id[ mp(_u[i], _v[i]) ] = i;
id[ mp(_v[i], _u[i]) ] = i;
}
while( mm >= nn ){
find_cycle();
eval();
vector < int > now;
for(int i = 0 ; i < cyc_len ; i++){
if( gold[ mp( cyc[i], cyc[i+1] ) ] ) {
now.pb(-1);
continue;
}
vector < int > query;
for(int j = 0 ; j < exc.size() ; j++) query.pb(exc[j]);
for(int j = 0 ; j < cyc_len ; j++){
if( i == j ) continue;
query.pb( id[mp( cyc[j], cyc[j+1] )] );
}
now.pb( count_common_roads(query) );
// cout << "Query : "; for(int i = 0 ; i < query.size() ; i++) cout << query[i];
// cout << endl << now.back() << endl;;
}
int f = -1;
for(int i = 1 ; i < cyc_len ; i++){
if( now[i] == -1 ){
f = i;
break;
}
if( now[i] != now[i-1] ){
if( now[i] < now[i-1] ) f = i;
else f = i-1;
break;
}
}
// cout << "! " << f << endl;
if( f == -1 ){
for(int i = 0 ; i < cyc_len ; i++){
v[ cyc[i] ][ cyc[i+1] ] = v[ cyc[i+1] ][ cyc[i] ] = 0;
mm--;
}
continue;
}
bool g = 1;
for(int i = f-1 ; i >= 0 ; i--){
if( now[i] != now[i+1] ) g = !g;
if( !g ){
v[ cyc[i] ][ cyc[i+1] ] = v[ cyc[i+1] ][ cyc[i] ] = 0;
mm--;
}
else{
gold[ mp( cyc[i], cyc[i+1] ) ] = 1;
gold[ mp( cyc[i+1], cyc[i] ) ] = 1;
}
}
g = 1;
for(int i = f+1 ; i < cyc_len ; i++){
if( now[i] != now[i-1] ) g = !g;
if( !g ){
v[ cyc[i] ][ cyc[i+1] ] = v[ cyc[i+1] ][ cyc[i] ] = 0;
mm--;
}
else{
gold[ mp( cyc[i], cyc[i+1] ) ] = 1;
gold[ mp( cyc[i+1], cyc[i] ) ] = 1;
}
}
}
vector < int > res;
for(int i = 0 ; i < nn ; i++){
for(int it = 0 ; it < i ; it++){
if( v[i][it] ) res.pb( id[ mp(it, i) ] );
}
}
// for(int i = 0 ; i < res.size() ; i++) cout << res[i] << ' ';
return res;
}
/*
6 6
0 1
1 2
2 3
3 4
0 4
0 5
0 1 2 3 5
4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 5
*/
Compilation message
simurgh.cpp: In function 'void find_cycle()':
simurgh.cpp:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < cw.size() ; i++) cyc.pb(cw[i]);
~~^~~~~~~~~~~
simurgh.cpp:22:28: warning: unused variable 'c' [-Wunused-variable]
int dep = 0, t1 = -1, t2, c;
^
simurgh.cpp: In function 'void eval()':
simurgh.cpp:78:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < cyc.size() ; i++) q.push(cyc[i]), p[cyc[i]] = cyc[i];
~~^~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:117:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0 ; j < exc.size() ; j++) query.pb(exc[j]);
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
488 KB |
correct |
| 2 |
Execution timed out |
3103 ms |
1049600 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
