oj.uz

Submission #582021

# Submission time Handle Problem Language Result Execution time Memory
582021 2022-06-23T09:36:19 Z alireza_kaviani Simurgh (IOI17_simurgh) C++17
100 / 100
 1953 ms 9400 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

#define SZ(x)	int((x).size())
#define X 		first
#define Y 		second
#define sep 	' '

const ll MAXN = 510; //TODO: fix MAXN

int n , m , common , mark[MAXN] , H[MAXN] , par[MAXN] , ind[MAXN] , tree[MAXN * MAXN] , ans[MAXN * MAXN];
vector<pii> E , adj[MAXN] , back_edge[MAXN];

int query(int A[]){
	vector<int> vec;
	for(int i = 0 ; i < m ; i++){
		if(A[i]){
			vec.push_back(i);
		}
	}
	//assert(SZ(vec) == n - 1);
	return count_common_roads(vec);
}

int query_back_edge(vector<pii> &v , int l , int r){
	assert(l > 0);
	int sum = common;
	for(int i = l ; i < r ; i++){
		tree[v[i].Y] = 1;
		tree[ind[v[i - 1].X]] = 0;
		sum -= ans[ind[v[i - 1].X]];
	}
	int res = query(tree);
	for(int i = l ; i < r ; i++){
		tree[v[i].Y] = 0;
		tree[ind[v[i - 1].X]] = 1;
	}
	return res - sum;
}

void DFS(int v){
	mark[v] = 1;
	for(pii i : adj[v]){
		int u = i.X , w = i.Y;
		if(mark[u]){
			continue;
		}
		//cout << v << sep << u << sep << w << endl;
		par[u] = v;
		ind[u] = w;
		tree[w] = 1;
		H[u] = H[v] + 1;
		DFS(u);
	}
}

void Calc(int v , int u , int index){
	int mx = common , W = -1 , x = v , flag = 1;
	while(x != u){
		if(ans[ind[x]] == -1){
			flag = 0;
		}
		x = par[x];
	}
	if(flag){
		return;
	}
	vector<pii> res;
	tree[index] = 1;
	x = v;
	while(x != u){
		if(ans[ind[x]] != -1){
			if(W != -1){
				res.push_back({W - ans[ind[x]] , x});
				x = par[x];
				continue;
			}
			tree[ind[x]] = 0;
			int cur = query(tree);
			tree[ind[x]] = 1;
			res.push_back({cur , x});
			W = cur + ans[ind[x]];
			x = par[x];
			continue;
		}
		tree[ind[x]] = 0;
		int cur = query(tree);
		tree[ind[x]] = 1;
		res.push_back({cur , x});
		x = par[x];
	}
	tree[index] = 0;
	//cout << "==========" << endl;
	//cout << v << sep << u << sep << index << endl;
	for(pii i : res){
		//cout << i.X << sep << i.Y << endl;
		mx = max(mx , i.X);
	}
	for(pii i : res){
		if(i.X == mx){
			ans[ind[i.Y]] = 0;
		}
		else{
			ans[ind[i.Y]] = 1;
		}
	}
	if(common == mx){
		ans[index] = 0;
	}
	else{
		ans[index] = 1;
	}
}

void solve(int v , int l , int r , int cnt){
	if(cnt == 0){
		return;
	}
	if(r - l == 1){
		ans[back_edge[v][l].Y] = 1;
		return;
	}
	int mid = l + r >> 1;
	int L = query_back_edge(back_edge[v] , l , mid) , R = cnt - L;
	solve(v , l , mid , L);
	solve(v , mid , r , R);
}

int cmp(pii x , pii y){
	return H[x.X] > H[y.X];
}

vector<int> find_roads(int N, vector<int> U, vector<int> V) {
	fill(ans , ans + MAXN * MAXN, -1);
	n = N; m = SZ(U);
	for(int i = 0 ; i < m ; i++){
		adj[V[i]].push_back({U[i] , i});
		adj[U[i]].push_back({V[i] , i});
		E.push_back({V[i] , U[i]});
	}
	DFS(0);
	common = query(tree);
	for(int i = 0 ; i < m ; i++){
		if(H[E[i].X] < H[E[i].Y]){
			swap(E[i].X , E[i].Y);
		}
	}
	for(int i = 0 ; i < m ; i++){
		if(tree[i] == 0){
			Calc(E[i].X , E[i].Y , i);
		}
	}
	for(int i = 0 ; i < n ; i++){
		back_edge[i].push_back({i , 0});
	}
	for(int i = 0 ; i < m ; i++){
		if(tree[i] == 1 && ans[i] == -1){
			ans[i] = 1;
		}
		if(ans[i] == -1){
			back_edge[E[i].X].push_back({E[i].Y , i});
		}
	}
	for(int i = 0 ; i < n ; i++){
		sort(back_edge[i].begin() , back_edge[i].end() , cmp);
		int cnt = query_back_edge(back_edge[i] , 1 , SZ(back_edge[i]));
		solve(i , 1 , SZ(back_edge[i]) , cnt);
	}
	vector<int> res;
	for(int i = 0 ; i < m ; i++){
		if(ans[i] == -1){
			ans[i] = 0;
		}
		if(ans[i]){
			res.push_back(i);
		}
	}
	return res;
}

Compilation message

simurgh.cpp: In function 'void solve(int, int, int, int)':
simurgh.cpp:128:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  128 |  int mid = l + r >> 1;
      |            ~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB correct
2 Correct 1 ms 1236 KB correct
3 Correct 1 ms 1236 KB correct
4 Correct 1 ms 1236 KB correct
5 Correct 1 ms 1236 KB correct
6 Correct 1 ms 1236 KB correct
7 Correct 1 ms 1236 KB correct
8 Correct 1 ms 1236 KB correct
9 Correct 1 ms 1236 KB correct
10 Correct 1 ms 1236 KB correct
11 Correct 1 ms 1236 KB correct
12 Correct 1 ms 1236 KB correct
13 Correct 1 ms 1236 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB correct
2 Correct 1 ms 1236 KB correct
3 Correct 1 ms 1236 KB correct
4 Correct 1 ms 1236 KB correct
5 Correct 1 ms 1236 KB correct
6 Correct 1 ms 1236 KB correct
7 Correct 1 ms 1236 KB correct
8 Correct 1 ms 1236 KB correct
9 Correct 1 ms 1236 KB correct
10 Correct 1 ms 1236 KB correct
11 Correct 1 ms 1236 KB correct
12 Correct 1 ms 1236 KB correct
13 Correct 1 ms 1236 KB correct
14 Correct 4 ms 1364 KB correct
15 Correct 3 ms 1364 KB correct
16 Correct 4 ms 1364 KB correct
17 Correct 4 ms 1364 KB correct
18 Correct 1 ms 1364 KB correct
19 Correct 3 ms 1364 KB correct
20 Correct 3 ms 1364 KB correct
21 Correct 2 ms 1364 KB correct
22 Correct 2 ms 1364 KB correct
23 Correct 2 ms 1364 KB correct
24 Correct 2 ms 1364 KB correct
25 Correct 1 ms 1364 KB correct
26 Correct 2 ms 1364 KB correct
27 Correct 2 ms 1364 KB correct
28 Correct 1 ms 1364 KB correct
29 Correct 1 ms 1364 KB correct
30 Correct 2 ms 1364 KB correct
31 Correct 2 ms 1364 KB correct
32 Correct 2 ms 1364 KB correct
33 Correct 2 ms 1364 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB correct
2 Correct 1 ms 1236 KB correct
3 Correct 1 ms 1236 KB correct
4 Correct 1 ms 1236 KB correct
5 Correct 1 ms 1236 KB correct
6 Correct 1 ms 1236 KB correct
7 Correct 1 ms 1236 KB correct
8 Correct 1 ms 1236 KB correct
9 Correct 1 ms 1236 KB correct
10 Correct 1 ms 1236 KB correct
11 Correct 1 ms 1236 KB correct
12 Correct 1 ms 1236 KB correct
13 Correct 1 ms 1236 KB correct
14 Correct 4 ms 1364 KB correct
15 Correct 3 ms 1364 KB correct
16 Correct 4 ms 1364 KB correct
17 Correct 4 ms 1364 KB correct
18 Correct 1 ms 1364 KB correct
19 Correct 3 ms 1364 KB correct
20 Correct 3 ms 1364 KB correct
21 Correct 2 ms 1364 KB correct
22 Correct 2 ms 1364 KB correct
23 Correct 2 ms 1364 KB correct
24 Correct 2 ms 1364 KB correct
25 Correct 1 ms 1364 KB correct
26 Correct 2 ms 1364 KB correct
27 Correct 2 ms 1364 KB correct
28 Correct 1 ms 1364 KB correct
29 Correct 1 ms 1364 KB correct
30 Correct 2 ms 1364 KB correct
31 Correct 2 ms 1364 KB correct
32 Correct 2 ms 1364 KB correct
33 Correct 2 ms 1364 KB correct
34 Correct 197 ms 3036 KB correct
35 Correct 186 ms 3144 KB correct
36 Correct 132 ms 2688 KB correct
37 Correct 10 ms 1360 KB correct
38 Correct 194 ms 3184 KB correct
39 Correct 151 ms 2944 KB correct
40 Correct 126 ms 2760 KB correct
41 Correct 84 ms 3184 KB correct
42 Correct 160 ms 3172 KB correct
43 Correct 60 ms 2516 KB correct
44 Correct 51 ms 2120 KB correct
45 Correct 57 ms 2292 KB correct
46 Correct 42 ms 2132 KB correct
47 Correct 19 ms 1684 KB correct
48 Correct 4 ms 1364 KB correct
49 Correct 7 ms 1364 KB correct
50 Correct 18 ms 1736 KB correct
51 Correct 57 ms 2292 KB correct
52 Correct 53 ms 2116 KB correct
53 Correct 44 ms 2020 KB correct
54 Correct 61 ms 2480 KB correct
55 Correct 55 ms 2308 KB correct
56 Correct 51 ms 2300 KB correct
57 Correct 50 ms 2264 KB correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB correct
2 Correct 1 ms 1236 KB correct
3 Correct 969 ms 6348 KB correct
4 Correct 1859 ms 9364 KB correct
5 Correct 1911 ms 9372 KB correct
6 Correct 1953 ms 9376 KB correct
7 Correct 1505 ms 9380 KB correct
8 Correct 1322 ms 9400 KB correct
9 Correct 1903 ms 9392 KB correct
10 Correct 1928 ms 9384 KB correct
11 Correct 1736 ms 9380 KB correct
12 Correct 1912 ms 9380 KB correct
13 Correct 1 ms 1364 KB correct
14 Correct 1665 ms 9364 KB correct
15 Correct 1913 ms 9388 KB correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB correct
2 Correct 1 ms 1236 KB correct
3 Correct 1 ms 1236 KB correct
4 Correct 1 ms 1236 KB correct
5 Correct 1 ms 1236 KB correct
6 Correct 1 ms 1236 KB correct
7 Correct 1 ms 1236 KB correct
8 Correct 1 ms 1236 KB correct
9 Correct 1 ms 1236 KB correct
10 Correct 1 ms 1236 KB correct
11 Correct 1 ms 1236 KB correct
12 Correct 1 ms 1236 KB correct
13 Correct 1 ms 1236 KB correct
14 Correct 4 ms 1364 KB correct
15 Correct 3 ms 1364 KB correct
16 Correct 4 ms 1364 KB correct
17 Correct 4 ms 1364 KB correct
18 Correct 1 ms 1364 KB correct
19 Correct 3 ms 1364 KB correct
20 Correct 3 ms 1364 KB correct
21 Correct 2 ms 1364 KB correct
22 Correct 2 ms 1364 KB correct
23 Correct 2 ms 1364 KB correct
24 Correct 2 ms 1364 KB correct
25 Correct 1 ms 1364 KB correct
26 Correct 2 ms 1364 KB correct
27 Correct 2 ms 1364 KB correct
28 Correct 1 ms 1364 KB correct
29 Correct 1 ms 1364 KB correct
30 Correct 2 ms 1364 KB correct
31 Correct 2 ms 1364 KB correct
32 Correct 2 ms 1364 KB correct
33 Correct 2 ms 1364 KB correct
34 Correct 197 ms 3036 KB correct
35 Correct 186 ms 3144 KB correct
36 Correct 132 ms 2688 KB correct
37 Correct 10 ms 1360 KB correct
38 Correct 194 ms 3184 KB correct
39 Correct 151 ms 2944 KB correct
40 Correct 126 ms 2760 KB correct
41 Correct 84 ms 3184 KB correct
42 Correct 160 ms 3172 KB correct
43 Correct 60 ms 2516 KB correct
44 Correct 51 ms 2120 KB correct
45 Correct 57 ms 2292 KB correct
46 Correct 42 ms 2132 KB correct
47 Correct 19 ms 1684 KB correct
48 Correct 4 ms 1364 KB correct
49 Correct 7 ms 1364 KB correct
50 Correct 18 ms 1736 KB correct
51 Correct 57 ms 2292 KB correct
52 Correct 53 ms 2116 KB correct
53 Correct 44 ms 2020 KB correct
54 Correct 61 ms 2480 KB correct
55 Correct 55 ms 2308 KB correct
56 Correct 51 ms 2300 KB correct
57 Correct 50 ms 2264 KB correct
58 Correct 1 ms 1236 KB correct
59 Correct 1 ms 1236 KB correct
60 Correct 969 ms 6348 KB correct
61 Correct 1859 ms 9364 KB correct
62 Correct 1911 ms 9372 KB correct
63 Correct 1953 ms 9376 KB correct
64 Correct 1505 ms 9380 KB correct
65 Correct 1322 ms 9400 KB correct
66 Correct 1903 ms 9392 KB correct
67 Correct 1928 ms 9384 KB correct
68 Correct 1736 ms 9380 KB correct
69 Correct 1912 ms 9380 KB correct
70 Correct 1 ms 1364 KB correct
71 Correct 1665 ms 9364 KB correct
72 Correct 1913 ms 9388 KB correct
73 Correct 1 ms 1236 KB correct
74 Correct 1911 ms 9364 KB correct
75 Correct 1789 ms 9192 KB correct
76 Correct 482 ms 4360 KB correct
77 Correct 1899 ms 9376 KB correct
78 Correct 1923 ms 9364 KB correct
79 Correct 1908 ms 9396 KB correct
80 Correct 1813 ms 9232 KB correct
81 Correct 1363 ms 8424 KB correct
82 Correct 1788 ms 9260 KB correct
83 Correct 861 ms 5600 KB correct
84 Correct 595 ms 6568 KB correct
85 Correct 515 ms 6212 KB correct
86 Correct 332 ms 4524 KB correct
87 Correct 260 ms 3744 KB correct
88 Correct 172 ms 3032 KB correct
89 Correct 169 ms 2988 KB correct
90 Correct 151 ms 2728 KB correct
91 Correct 23 ms 1500 KB correct
92 Correct 15 ms 1436 KB correct
93 Correct 510 ms 6200 KB correct
94 Correct 326 ms 4528 KB correct
95 Correct 344 ms 4500 KB correct
96 Correct 158 ms 2928 KB correct
97 Correct 174 ms 3068 KB correct
98 Correct 244 ms 3708 KB correct
99 Correct 182 ms 3144 KB correct
100 Correct 48 ms 1812 KB correct
101 Correct 15 ms 1464 KB correct
102 Correct 455 ms 5456 KB correct
103 Correct 455 ms 5464 KB correct
104 Correct 420 ms 5404 KB correct
105 Correct 450 ms 5420 KB correct