oj.uz

Submission #1043702

# Submission time Handle Problem Language Result Execution time Memory
1043702 2024-08-04T14:20:36 Z Mr_Husanboy Simurgh (IOI17_simurgh) C++17
0 / 100
 0 ms 348 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;
	}
};


vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	vector<int> royal;
	int m = len(u);
	DSU roy(n);
	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 ++){
			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]]);
				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;
				int mx = 0;
				for(int k = 0; k < len(mp[j]); k ++){
					if(roy.get(u[mp[j][k]]) == roy.get(v[mp[j][k]])) continue;
					gs.push_back(mp[j][k]);
					assert(len(gs)==n - 1);
					int cnt = count_common_roads(gs);
					counts.push_back({cnt, mp[j][k]});
					mx = max(mx, cnt);
					gs.pop_back();
				}
				for(auto [cnt, k] : counts){
					if(cnt == mx){
						royal.push_back(k);
						roy.unite(u[k], v[k]);
					}
				}

				for(int k = 0; k < len(mp) - 1; k ++){
					gs.pop_back();
				}
			}
		}
	}
	assert(len(royal) == n - 1);
	return royal;
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 17.0

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

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 Incorrect 0 ms 348 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB correct
2 Incorrect 0 ms 348 KB WA in grader: NO
3 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 Incorrect 0 ms 348 KB WA in grader: NO
4 Halted 0 ms 0 KB -