답안 #1036679

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1036679	2024-07-27T15:25:18 Z	Alihan_8	Simurgh (IOI17_simurgh)	C++17	51 / 100	432 ms	31940 KB

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.0 / 13.0

#	결과	메모리	Grader output
1	Correct	348 KB	correct
2	Correct	436 KB	correct
3	Correct	348 KB	correct
4	Correct	348 KB	correct
5	Correct	348 KB	correct
6	Correct	436 KB	correct
7	Correct	348 KB	correct
8	Correct	348 KB	correct
9	Correct	348 KB	correct
10	Correct	348 KB	correct
11	Correct	348 KB	correct
12	Correct	352 KB	correct
13	Correct	348 KB	correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	correct
2	Correct	0 ms	436 KB	correct
3	Correct	0 ms	348 KB	correct
4	Correct	0 ms	348 KB	correct
5	Correct	0 ms	348 KB	correct
6	Correct	0 ms	436 KB	correct
7	Correct	0 ms	348 KB	correct
8	Correct	0 ms	348 KB	correct
9	Correct	0 ms	348 KB	correct
10	Correct	0 ms	348 KB	correct
11	Correct	0 ms	348 KB	correct
12	Correct	0 ms	352 KB	correct
13	Correct	0 ms	348 KB	correct
14	Correct	5 ms	856 KB	correct
15	Correct	4 ms	860 KB	correct
16	Correct	4 ms	804 KB	correct
17	Correct	4 ms	604 KB	correct
18	Correct	1 ms	432 KB	correct
19	Correct	5 ms	692 KB	correct
20	Correct	3 ms	604 KB	correct
21	Correct	4 ms	756 KB	correct
22	Correct	3 ms	604 KB	correct
23	Correct	3 ms	600 KB	correct
24	Correct	2 ms	436 KB	correct
25	Correct	0 ms	348 KB	correct
26	Correct	2 ms	604 KB	correct
27	Correct	2 ms	604 KB	correct
28	Correct	1 ms	488 KB	correct
29	Correct	1 ms	348 KB	correct
30	Correct	2 ms	600 KB	correct
31	Correct	3 ms	604 KB	correct
32	Correct	2 ms	604 KB	correct
33	Correct	2 ms	604 KB	correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	correct
2	Correct	0 ms	436 KB	correct
3	Correct	0 ms	348 KB	correct
4	Correct	0 ms	348 KB	correct
5	Correct	0 ms	348 KB	correct
6	Correct	0 ms	436 KB	correct
7	Correct	0 ms	348 KB	correct
8	Correct	0 ms	348 KB	correct
9	Correct	0 ms	348 KB	correct
10	Correct	0 ms	348 KB	correct
11	Correct	0 ms	348 KB	correct
12	Correct	0 ms	352 KB	correct
13	Correct	0 ms	348 KB	correct
14	Correct	5 ms	856 KB	correct
15	Correct	4 ms	860 KB	correct
16	Correct	4 ms	804 KB	correct
17	Correct	4 ms	604 KB	correct
18	Correct	1 ms	432 KB	correct
19	Correct	5 ms	692 KB	correct
20	Correct	3 ms	604 KB	correct
21	Correct	4 ms	756 KB	correct
22	Correct	3 ms	604 KB	correct
23	Correct	3 ms	600 KB	correct
24	Correct	2 ms	436 KB	correct
25	Correct	0 ms	348 KB	correct
26	Correct	2 ms	604 KB	correct
27	Correct	2 ms	604 KB	correct
28	Correct	1 ms	488 KB	correct
29	Correct	1 ms	348 KB	correct
30	Correct	2 ms	600 KB	correct
31	Correct	3 ms	604 KB	correct
32	Correct	2 ms	604 KB	correct
33	Correct	2 ms	604 KB	correct
34	Correct	406 ms	31768 KB	correct
35	Correct	432 ms	30752 KB	correct
36	Correct	235 ms	21328 KB	correct
37	Correct	13 ms	1884 KB	correct
38	Correct	391 ms	31940 KB	correct
39	Correct	380 ms	27072 KB	correct
40	Correct	238 ms	21464 KB	correct
41	Correct	368 ms	31668 KB	correct
42	Correct	392 ms	31808 KB	correct
43	Correct	186 ms	16976 KB	correct
44	Correct	150 ms	13648 KB	correct
45	Correct	185 ms	16036 KB	correct
46	Correct	109 ms	12264 KB	correct
47	Correct	47 ms	5416 KB	correct
48	Correct	4 ms	604 KB	correct
49	Correct	13 ms	1880 KB	correct
50	Correct	49 ms	5644 KB	correct
51	Correct	182 ms	15956 KB	correct
52	Correct	195 ms	13648 KB	correct
53	Correct	131 ms	12116 KB	correct
54	Correct	197 ms	17036 KB	correct
55	Correct	174 ms	16108 KB	correct
56	Correct	166 ms	16212 KB	correct
57	Correct	165 ms	16176 KB	correct

Subtask #4
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	correct
2	Correct	0 ms	604 KB	correct
3	Incorrect	276 ms	25432 KB	WA in grader: NO
4	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	correct
2	Correct	0 ms	436 KB	correct
3	Correct	0 ms	348 KB	correct
4	Correct	0 ms	348 KB	correct
5	Correct	0 ms	348 KB	correct
6	Correct	0 ms	436 KB	correct
7	Correct	0 ms	348 KB	correct
8	Correct	0 ms	348 KB	correct
9	Correct	0 ms	348 KB	correct
10	Correct	0 ms	348 KB	correct
11	Correct	0 ms	348 KB	correct
12	Correct	0 ms	352 KB	correct
13	Correct	0 ms	348 KB	correct
14	Correct	5 ms	856 KB	correct
15	Correct	4 ms	860 KB	correct
16	Correct	4 ms	804 KB	correct
17	Correct	4 ms	604 KB	correct
18	Correct	1 ms	432 KB	correct
19	Correct	5 ms	692 KB	correct
20	Correct	3 ms	604 KB	correct
21	Correct	4 ms	756 KB	correct
22	Correct	3 ms	604 KB	correct
23	Correct	3 ms	600 KB	correct
24	Correct	2 ms	436 KB	correct
25	Correct	0 ms	348 KB	correct
26	Correct	2 ms	604 KB	correct
27	Correct	2 ms	604 KB	correct
28	Correct	1 ms	488 KB	correct
29	Correct	1 ms	348 KB	correct
30	Correct	2 ms	600 KB	correct
31	Correct	3 ms	604 KB	correct
32	Correct	2 ms	604 KB	correct
33	Correct	2 ms	604 KB	correct
34	Correct	406 ms	31768 KB	correct
35	Correct	432 ms	30752 KB	correct
36	Correct	235 ms	21328 KB	correct
37	Correct	13 ms	1884 KB	correct
38	Correct	391 ms	31940 KB	correct
39	Correct	380 ms	27072 KB	correct
40	Correct	238 ms	21464 KB	correct
41	Correct	368 ms	31668 KB	correct
42	Correct	392 ms	31808 KB	correct
43	Correct	186 ms	16976 KB	correct
44	Correct	150 ms	13648 KB	correct
45	Correct	185 ms	16036 KB	correct
46	Correct	109 ms	12264 KB	correct
47	Correct	47 ms	5416 KB	correct
48	Correct	4 ms	604 KB	correct
49	Correct	13 ms	1880 KB	correct
50	Correct	49 ms	5644 KB	correct
51	Correct	182 ms	15956 KB	correct
52	Correct	195 ms	13648 KB	correct
53	Correct	131 ms	12116 KB	correct
54	Correct	197 ms	17036 KB	correct
55	Correct	174 ms	16108 KB	correct
56	Correct	166 ms	16212 KB	correct
57	Correct	165 ms	16176 KB	correct
58	Correct	0 ms	348 KB	correct
59	Correct	0 ms	604 KB	correct
60	Incorrect	276 ms	25432 KB	WA in grader: NO
61	Halted	0 ms	0 KB	-

답안 #1036679

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 17.0 / 17.0

Subtask #3 21.0 / 21.0

Subtask #4 0 / 19.0

Subtask #5 0 / 30.0

Subtask #1
13.0 / 13.0

Subtask #2
17.0 / 17.0

Subtask #3
21.0 / 21.0

Subtask #4
0 / 19.0

Subtask #5
0 / 30.0