Submission #61023

#TimeUsernameProblemLanguageResultExecution timeMemory
61023tugushkaSimurgh (IOI17_simurgh)C++14
30 / 100
3021 ms4348 KiB
#include "simurgh.h" #include<bits/stdc++.h> #define mp make_pair #define pb push_back using namespace std; typedef pair < int, int > pii; vector < int > cyc, exc; int nn, mm, p[255], d[255], cyc_len, id[255][255], gold[255][255]; bool v[255][255]; 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[u][it] ); q.push(it); } } } } vector<int> find_roads(int _n, vector<int> _u, vector<int> _v) { memset( id, -1, sizeof(id) ); memset( gold, -1, sizeof(gold) ); nn = _n; mm = _u.size(); for(int i = 0 ; i < mm ; i++){ v[_u[i]][_v[i]] = v[_v[i]][_u[i]] = 1; id[_u[i]][_v[i]] = id[_v[i]][_u[i]] = i; } while( mm >= nn ){ find_cycle(); eval(); vector < int > now; for(int i = 0 ; i < cyc_len ; i++){ if( gold[cyc[i]][cyc[i+1]] != -1 ) { now.pb(-1); // cout << "Gold" << ' ' << cyc[i] << ' ' << cyc[i+1] << endl; 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[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 _mn = 1e9, _mx = -1e9; for(int i = 0 ; i < cyc_len ; i++){ if( now[i] != -1 ) { _mn = min( _mn, now[i] ); _mx = max( _mx, now[i] ); } } // cout << s.size() << endl; if( _mn == _mx ){ for(int i = 0 ; i < cyc_len ; i++){ if( now[i] == -1 ) continue; v[ cyc[i] ][ cyc[i+1] ] = v[ cyc[i+1] ][ cyc[i] ] = 0; mm--; } continue; } else{ for(int i = 0 ; i < cyc_len ; i++){ if( now[i] == -1 ){ now[i] = _mn; } } } 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[cyc[i]][cyc[i+1]] = gold[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[cyc[i]][cyc[i+1]] = gold[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[it][i] ); } } // for(int i = 0 ; i < res.size() ; i++) cout << res[i] << ' '; return res; }

Compilation message (stderr)

simurgh.cpp: In function 'void find_cycle()':
simurgh.cpp:61: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:20:28: warning: unused variable 'c' [-Wunused-variable]
  int dep = 0, t1 = -1, t2, c;
                            ^
simurgh.cpp: In function 'void eval()':
simurgh.cpp:74: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:115: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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...