Submission #1036679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036679		Alihan_8	Simurgh (IOI17_simurgh)	C++17	51 / 100	432 ms	31940 KiB

simurgh

#include "simurgh.h"

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

map <vector<int>,int> dp;

int f(vector <int> x){
	sort(all(x));
	
	if ( !dp.count(x) ){
		dp[x] = count_common_roads(x);
	}
	
	return dp[x];
}



vector<int> find_roads(int n, std::vector<int> U, std::vector<int> V){
	int m = U.size();
	
	vector <int> g(m, -1);
	
	vector <vector<ar<int,2>>> adj(n);
	
	for ( int i = 0; i < m; i++ ){
		adj[U[i]].pb({V[i], i});
		adj[V[i]].pb({U[i], i});
	}
	
	vector <int> tree, us(n), d(n);
	
	vector <ar<int,2>> fa(n);
	
	vector <ar<int,4>> low(n);
	
	vector <vector<ar<int,2>>> to(n), alTo(n);
	
	auto dfs = [&](auto dfs, int u, int p) -> void{
		us[u] = true;
	
		low[u] = {d[u], u, -1};
		
		for ( auto &[v, j]: adj[u] ){
			if ( p != v ){
				if ( !us[v] ){
					d[v] = d[u] + 1;
					fa[v] = {u, j};
					
					tree.pb(j);
					
					dfs(dfs, v, u);
					
					if ( low[u][0] > low[v][0] ){
						low[u] = low[v];
					}
				} else if ( d[v] < d[u] ){
					if ( low[u][0] > d[v] ){
						low[u] = {d[v], v, j, u};
					}
					
					alTo[u].pb({v, j});
				}
			}
		}
		
		auto [dp, v, i, c] = low[u];
		
		if ( d[v] < d[u] ){
			to[c].pb({v, i});
		}
	};
	
	dfs(dfs, 0, -1);
	
	int X = f(tree);
	
	for ( int u = 0; u < n; u++ ){
		for ( auto &[v, j]: to[u] ){	
			vector <int> t;
			
			int x = u;	
			
			while ( x != v ){
				auto [nxt, i] = fa[x];
				
				t.pb(i);
				
				swap(nxt, x);
			}
			
			vector <int> us(m);
			
			for ( auto &x: t ){
				us[x] = true;
			}
			
			auto tmp = tree;
			
			for ( int i = 0; i < (int)tmp.size(); i++ ){
				int x = tmp[i];
				
				if ( !us[x] ) continue;
				
				if ( g[x] != -1 ){
					tmp[i] = j; int Y = f(tmp);
					tmp[i] = tree[i];
					
					if ( X == Y ){
						g[j] = g[x];
					} else{
						g[j] = (X < Y);
					} break;
				}
			}
			
			if ( g[j] == -1 ){
				bool is = false;
				
				for ( int i = 0; i < (int)tmp.size(); i++ ){
					int x = tmp[i];
					
					if ( !us[x] ) continue;
					
					tmp[i] = j; int Y = f(tmp);
					tmp[i] = tree[i];
					
					if ( X > Y ) g[x] = 1, g[j] = 0;
					
					if ( X < Y ) g[x] = 0, g[j] = 1;
					
					is |= (X != Y);
				}
				
				if ( !is ){
					g[j] = 0;
					
					for ( auto &x: t ){
						g[x] = 0;
					}
				}
				
				continue;
			}
			
			for ( int i = 0; i < (int)tmp.size(); i++ ){
				int x = tmp[i];
				
				if ( !us[x] || g[x] != -1 ) continue;
				
				tmp[i] = j; int Y = f(tmp);
				tmp[i] = tree[i];
				
				if ( X == Y ){
					g[x] = g[j];
				} else{
					g[x] = (X > Y);
				}
			}
		}
	}
	
	for ( int u = 0; u < n; u++ ){
		for ( auto &[v, j]: alTo[u] ){
			if ( g[j] != -1 ) continue;
				
			vector <int> t;
			
			int x = u;	
			
			while ( x != v ){
				auto [nxt, i] = fa[x];
				
				t.pb(i);
				
				swap(nxt, x);
			}
			
			vector <int> us(m);
			
			for ( auto &x: t ){
				us[x] = true;
			}
			
			auto tmp = tree;
			
			for ( int i = 0; i < (int)tmp.size(); i++ ){
				int x = tmp[i];
				
				if ( !us[x] ) continue;
				
				if ( g[x] != -1 ){
					tmp[i] = j; int Y = f(tmp);
					tmp[i] = tree[i];
					
					if ( X == Y ){
						g[j] = g[x];
					} else{
						g[j] = (X < Y);
					} break;
				}
			}
			
			if ( g[j] == -1 ){
				continue;
			}
			
			for ( int i = 0; i < (int)tmp.size(); i++ ){
				int x = tmp[i];
				
				if ( !us[x] || g[x] != -1 ) continue;
				
				tmp[i] = j; int Y = f(tmp);
				tmp[i] = tree[i];
				
				if ( X == Y ){
					g[x] = g[j];
				} else{
					g[x] = (X > Y);
				}
			}
		}
	}
	
	vector <int> ret;
	
	for ( int i = 0; i < m; i++ ){
		if ( g[i] == -1 ){
			g[i] = 1;
		}
		
		if ( g[i] > 0 ){
			ret.pb(i);
		}
	}
	
	//sort(all(ret)); for ( auto &x: ret ) cout << x << ' '; cout << ln;
	
	return ret;
}

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