oj.uz

Submission #1043828

# Submission time Handle Problem Language Result Execution time Memory
1043828 2024-08-04T20:19:32 Z Mr_Husanboy Simurgh (IOI17_simurgh) C++17
30 / 100
 71 ms 2020 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
 
using namespace std;
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
 
#define ll long long
 
template<typename T>
int len(T &a){
	return a.size();
}
 
struct DSU{
	vector<int> par, sz; int n;
	DSU (int _n){
		n = _n;
		par.resize(n);
		iota(all(par), 0);
		sz.assign(n, 1);
	}
	DSU (){}
	int get(int a){
		return (par[a] == a ? a : par[a] = get(par[a]));
	}
 
	void init(int _n){
		n = _n;
		par.resize(n);
		iota(all(par), 0);
		sz.assign(n, 1);
	}
 
	void unite(int a, int b){
		a = get(a);
		b = get(b);
		if(a == b) return;
		if(sz[a] < sz[b]) swap(a,b);
		sz[a] += sz[b];
		par[b] = a;
	}
 
	void link(int a, int b){
		a = get(a); b = get(b);
		if(a == b) return;
		sz[b] += sz[a];
		par[a] = b;
	}
};
 
 int _qu = 0;
int ask(const vector<int> &gs){
	_qu ++;
	assert(_qu <= 30000);
	return count_common_roads(gs);
}
 
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	vector<int> royal;
	int m = len(u);
	DSU roy(n);
	vector<int> in(m);
	for(int i = 0; i < n - 1; i ++){
		DSU t(n);
		vector<int> gs;
		vector<int> rem;
		for(int j = 0; j < m; j ++){
			if(u[j] == i || v[j] == i){
				rem.push_back(j);
			}else{
				if(t.get(v[j]) == t.get(u[j])) continue;
				gs.push_back(j);
				t.unite(v[j], u[j]);
			}
		}
		vector<vector<int>> mp;
		map<int,int> id;
		for(auto j : rem){
			//cout<<j << ' ';
			int p = t.get(u[j] ^ v[j] ^ i);
			if(id.count(p) == 0){
				id[p] = len(id);
				mp.push_back(vector<int>());
			}
			mp[id[p]].push_back(j);
		}
		for(int j = 0; j < len(mp); j ++){
			int f = -1;
			if(len(mp[j]) == 1){
				if(roy.get(u[mp[j][0]]) == roy.get(v[mp[j][0]])){
					continue;
				}
				royal.push_back(mp[j][0]);
				roy.unite(u[mp[j][0]], v[mp[j][0]]);
				in[mp[j][0]] = 1;
				continue;
			}else{
				for(int k = 0; k < len(mp); k ++){
					if(k == j){
						continue;
					}
					gs.push_back(mp[k][0]);
				}
				vector<pair<int,int>> counts;
				for(int k = 0; k < len(mp[j]); k ++){
					if(in[mp[j][k]]) {f = mp[j][k]; break;};
				}
				if(f == -1){
					int mx = 0;
					vector<pair<int,int>> counts;
					for(auto k : mp[j]){
						gs.push_back(k);
						int cnt = ask(gs);
						counts.push_back({cnt, k});
						gs.pop_back();
						if(cnt > mx){
							mx = cnt;
						}
					}
					for(auto [cnt, k] : counts){
						if(cnt == mx){
							royal.push_back(k);
							roy.unite(u[k], v[k]);
							in[k] =1;
						}
					}
				}else{
					gs.push_back(f);
					int mx = ask(gs);
					gs.pop_back();
					for(auto k : mp[j]){
						if(roy.get(u[k]) == roy.get(v[k])) continue;
						gs.push_back(k);
						if(ask(gs) == mx){
							royal.push_back(k);
							roy.unite(u[k], v[k]);
							in[k] = 1;
						}
						gs.pop_back();
					}
				}
 
				for(int k = 0; k < len(mp) - 1; k ++){
					gs.pop_back();
				}
			}
		}
	}
	assert(len(royal) == n - 1);
	return royal;
}

Subtask #1
13.0 / 13.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 1 ms 348 KB correct
12 Correct 0 ms 348 KB correct
13 Correct 0 ms 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 1 ms 348 KB correct
12 Correct 0 ms 348 KB correct
13 Correct 0 ms 348 KB correct
14 Correct 1 ms 348 KB correct
15 Correct 1 ms 344 KB correct
16 Correct 1 ms 348 KB correct
17 Correct 1 ms 344 KB correct
18 Correct 0 ms 348 KB correct
19 Correct 1 ms 348 KB correct
20 Correct 1 ms 344 KB correct
21 Correct 1 ms 348 KB correct
22 Correct 1 ms 344 KB correct
23 Correct 1 ms 348 KB correct
24 Correct 1 ms 348 KB correct
25 Correct 0 ms 348 KB correct
26 Correct 1 ms 348 KB correct
27 Correct 1 ms 348 KB correct
28 Correct 1 ms 344 KB correct
29 Correct 0 ms 348 KB correct
30 Correct 1 ms 348 KB correct
31 Correct 1 ms 348 KB correct
32 Correct 1 ms 348 KB correct
33 Correct 1 ms 388 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 1 ms 348 KB correct
12 Correct 0 ms 348 KB correct
13 Correct 0 ms 348 KB correct
14 Correct 1 ms 348 KB correct
15 Correct 1 ms 344 KB correct
16 Correct 1 ms 348 KB correct
17 Correct 1 ms 344 KB correct
18 Correct 0 ms 348 KB correct
19 Correct 1 ms 348 KB correct
20 Correct 1 ms 344 KB correct
21 Correct 1 ms 348 KB correct
22 Correct 1 ms 344 KB correct
23 Correct 1 ms 348 KB correct
24 Correct 1 ms 348 KB correct
25 Correct 0 ms 348 KB correct
26 Correct 1 ms 348 KB correct
27 Correct 1 ms 348 KB correct
28 Correct 1 ms 344 KB correct
29 Correct 0 ms 348 KB correct
30 Correct 1 ms 348 KB correct
31 Correct 1 ms 348 KB correct
32 Correct 1 ms 348 KB correct
33 Correct 1 ms 388 KB correct
34 Runtime error 71 ms 1496 KB Execution killed with signal 6
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Incorrect 71 ms 2020 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 1 ms 348 KB correct
12 Correct 0 ms 348 KB correct
13 Correct 0 ms 348 KB correct
14 Correct 1 ms 348 KB correct
15 Correct 1 ms 344 KB correct
16 Correct 1 ms 348 KB correct
17 Correct 1 ms 344 KB correct
18 Correct 0 ms 348 KB correct
19 Correct 1 ms 348 KB correct
20 Correct 1 ms 344 KB correct
21 Correct 1 ms 348 KB correct
22 Correct 1 ms 344 KB correct
23 Correct 1 ms 348 KB correct
24 Correct 1 ms 348 KB correct
25 Correct 0 ms 348 KB correct
26 Correct 1 ms 348 KB correct
27 Correct 1 ms 348 KB correct
28 Correct 1 ms 344 KB correct
29 Correct 0 ms 348 KB correct
30 Correct 1 ms 348 KB correct
31 Correct 1 ms 348 KB correct
32 Correct 1 ms 348 KB correct
33 Correct 1 ms 388 KB correct
34 Runtime error 71 ms 1496 KB Execution killed with signal 6
35 Halted 0 ms 0 KB -