Submission #1036608

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1036608	2024-07-27T14:47:07 Z	Alihan_8	Simurgh (IOI17_simurgh)	C++17	30 / 100	373 ms	32828 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 <vector<ar<int,2>>> to(n);
	
	auto dfs = [&](auto dfs, int u, int p) -> void{
		us[u] = true;
		
		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);
				} else if ( d[v] < d[u] ){
					to[u].pb({v, j});
				}
			}
		}
	};
	
	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);
			}
			
			bool is = false;
			
			for ( auto &x: t ){
				auto tmp = tree;
				
				for ( auto &i: tmp ){
					if ( i == x ){
						i = j;
						
						break;
					}
				}
				
				int Y = f(tmp);
				
				if ( Y > X ){
					g[j] = 1, g[x] = 0;
				} 
				
				if ( Y < X ){
					g[x] = 1, g[j] = 0;
				}
				
				is |= (X != Y);
			}
			
			if ( !is ){
				g[j] = 0;
				
				for ( auto &x: t ){
					g[x] = 0;
				}
			}
		}
	}
	
	vector <int> ret;
	
	for ( int i = 0; i < m; i++ ){
		if ( g[i] == -1 ){
			g[i] = 1;
		}
		
		if ( g[i] > 0 ){
			ret.pb(i);
		}
	}
	
	return ret;
}

Subtask #1
13.0 / 13.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	correct
2	Correct	348 KB	correct
3	Correct	348 KB	correct
4	Correct	348 KB	correct
5	Correct	348 KB	correct
6	Correct	348 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	348 KB	correct
13	Correct	348 KB	correct

Subtask #2
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	correct
2	Correct	0 ms	348 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	348 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	348 KB	correct
13	Correct	0 ms	348 KB	correct
14	Correct	52 ms	6336 KB	correct
15	Correct	58 ms	6228 KB	correct
16	Correct	52 ms	6120 KB	correct
17	Correct	42 ms	5176 KB	correct
18	Correct	14 ms	1884 KB	correct
19	Correct	47 ms	5312 KB	correct
20	Correct	40 ms	4948 KB	correct
21	Correct	38 ms	4688 KB	correct
22	Correct	18 ms	2396 KB	correct
23	Correct	14 ms	1976 KB	correct
24	Correct	12 ms	1884 KB	correct
25	Correct	0 ms	436 KB	correct
26	Correct	12 ms	1884 KB	correct
27	Correct	14 ms	1884 KB	correct
28	Correct	3 ms	604 KB	correct
29	Correct	1 ms	448 KB	correct
30	Correct	26 ms	3312 KB	correct
31	Correct	25 ms	3164 KB	correct
32	Correct	29 ms	3160 KB	correct
33	Correct	28 ms	3156 KB	correct

Subtask #3
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	correct
2	Correct	0 ms	348 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	348 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	348 KB	correct
13	Correct	0 ms	348 KB	correct
14	Correct	52 ms	6336 KB	correct
15	Correct	58 ms	6228 KB	correct
16	Correct	52 ms	6120 KB	correct
17	Correct	42 ms	5176 KB	correct
18	Correct	14 ms	1884 KB	correct
19	Correct	47 ms	5312 KB	correct
20	Correct	40 ms	4948 KB	correct
21	Correct	38 ms	4688 KB	correct
22	Correct	18 ms	2396 KB	correct
23	Correct	14 ms	1976 KB	correct
24	Correct	12 ms	1884 KB	correct
25	Correct	0 ms	436 KB	correct
26	Correct	12 ms	1884 KB	correct
27	Correct	14 ms	1884 KB	correct
28	Correct	3 ms	604 KB	correct
29	Correct	1 ms	448 KB	correct
30	Correct	26 ms	3312 KB	correct
31	Correct	25 ms	3164 KB	correct
32	Correct	29 ms	3160 KB	correct
33	Correct	28 ms	3156 KB	correct
34	Incorrect	373 ms	32828 KB	WA in grader: NO
35	Halted	0 ms	0 KB	-

Subtask #4
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	correct
2	Correct	1 ms	344 KB	correct
3	Incorrect	231 ms	24984 KB	WA in grader: NO
4	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	correct
2	Correct	0 ms	348 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	348 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	348 KB	correct
13	Correct	0 ms	348 KB	correct
14	Correct	52 ms	6336 KB	correct
15	Correct	58 ms	6228 KB	correct
16	Correct	52 ms	6120 KB	correct
17	Correct	42 ms	5176 KB	correct
18	Correct	14 ms	1884 KB	correct
19	Correct	47 ms	5312 KB	correct
20	Correct	40 ms	4948 KB	correct
21	Correct	38 ms	4688 KB	correct
22	Correct	18 ms	2396 KB	correct
23	Correct	14 ms	1976 KB	correct
24	Correct	12 ms	1884 KB	correct
25	Correct	0 ms	436 KB	correct
26	Correct	12 ms	1884 KB	correct
27	Correct	14 ms	1884 KB	correct
28	Correct	3 ms	604 KB	correct
29	Correct	1 ms	448 KB	correct
30	Correct	26 ms	3312 KB	correct
31	Correct	25 ms	3164 KB	correct
32	Correct	29 ms	3160 KB	correct
33	Correct	28 ms	3156 KB	correct
34	Incorrect	373 ms	32828 KB	WA in grader: NO
35	Halted	0 ms	0 KB	-

Submission #1036608

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 17.0 / 17.0

Subtask #3 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
0 / 21.0

Subtask #4
0 / 19.0

Subtask #5
0 / 30.0