Submission #60994

#	Time	Username	Problem	Language	Result	Execution time	Memory
60994		tugushka	Simurgh (IOI17_simurgh)	C++14	30 / 100	3028 ms	12704 KiB

simurgh

#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);
//				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[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;;
		}
		
		set < int > s;
		for(int i = 0 ; i < cyc_len ; i++){
			if( now[i] != -1 ) s.insert(now[i]);
		}
		
//		cout << s.size() << endl;
		
		if( s.size() == 1 ){
			
			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] = *s.begin();
				}
			}
		}
		
		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


6 8
0 1
1 2
2 3
3 4
0 4
0 5
0 3
4 5
0 5 4 6 2

4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 5

*/

Compilation message (stderr)

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:76: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:116:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j < exc.size() ; j++) query.pb(exc[j]);
                    ~~^~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30