| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 60522 |
2018-07-24T09:47:12 Z |
tugushka |
Simurgh (IOI17_simurgh) |
C++14 |
|
3000 ms |
991364 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;
vector < set < int > > v;
vector < int > cyc, exc;
int gold[25005], nn, mm, p[505], d[505], cyc_len;
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( set < int > :: iterator it = v[u].begin() ; it != v[u].end() ; it++ ){
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( set < int > :: iterator it = v[u].begin() ; it != v[u].end() ; it++ ){
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;
v.resize(nn);
memset(gold, -1, sizeof(gold));
mm = _u.size();
for(int i = 0 ; i < mm ; i++){
v[_u[i]].insert(_v[i]);
v[_v[i]].insert(_u[i]);
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++){
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] != now[i-1] ){
if( now[i] < now[i-1] ) f = i;
else f = i-1;
break;
}
}
if( f == -1 ){
for(int i = 0 ; i < cyc_len ; i++){
v[ cyc[i] ].erase( cyc[i+1] );
v[ cyc[i+1] ].erase( cyc[i] );
}
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] ].erase( cyc[i+1] );
v[ cyc[i+1] ].erase( cyc[i] );
}
}
g = 1;
for(int i = f+1 ; i < cyc_len ; i++){
if( now[i] != now[i-1] ) g = !g;
if( !g ){
v[ cyc[i] ].erase( cyc[i+1] );
v[ cyc[i+1] ].erase( cyc[i] );
}
}
system("pause");
}
vector < int > res;
return res;
}
/*
6 6
0 1
1 2
2 3
3 4
0 4
0 5
0 1 2 3 5
*/
Compilation message
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:66:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < cyc.size() ; i++) cout << cyc[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: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:108:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0 ; j < exc.size() ; j++) query.pb(exc[j]);
~~^~~~~~~~~~~~
simurgh.cpp:116:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
cout << "Query : "; for(int i = 0 ; i < query.size() ; i++) cout << query[i];
~~^~~~~~~~~~~~~~
simurgh.cpp:154:9: warning: ignoring return value of 'int system(const char*)', declared with attribute warn_unused_result [-Wunused-result]
system("pause");
~~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3099 ms |
991364 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3099 ms |
991364 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3099 ms |
991364 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
991364 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3099 ms |
991364 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
