Submission #423867

#	Time	Username	Problem	Language	Result	Execution time	Memory
423867		AugustinasJucas	Simurgh (IOI17_simurgh)	C++14	51 / 100	455 ms	5268 KiB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;
int N;
const int dydis = 501;
vector<pair<int, int> > brn;
vector<int> zn(dydis * dydis, -1);
vector<pair<int, int> > gr[dydis];
vector<int> tikrai;
int tevas[dydis];
int fP(int v){
	if(tevas[v] == v) return v;
	return tevas[v] = fP(tevas[v]);
}
void conn(int a, int b){
	a = fP(a);
	b = fP(b);
	if(a == b) return;
	tevas[a] = b;
}
set<int> virs;
bool vis[dydis] = {0};
int deg[dydis] = {0};
void form(){
	for(int i = 0; i < N; i++) {
		gr[i].clear();
		vis[i] = 0;
		deg[i] = 0;
	}
	virs.clear();
//	cout << "grafas:\n";
	for(int i = 0; i < (int) brn.size(); i++){
		if(zn[i] != -1) continue;
		int a = fP(brn[i].first);
		int b = fP(brn[i].second);
		if(a == b) continue;
		gr[a].push_back({b, i});
		gr[b].push_back({a, i});
//		cout << a << " -- " << b << endl;
		virs.insert(a); virs.insert(b);
	}
	//cout << endl;
}
vector<int> pl;
void dfs(int v){
	vis[v] = 1;
	for(auto x : gr[v]){
		if(vis[x.first]) continue;
		pl.push_back(x.second);
		deg[v]++;
		deg[x.first]++;
		dfs(x.first);
	}
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	//count_common_roads
	N = n;
	vector<int> ret;
	for(int i = 0; i < N; i++) tevas[i] = i;
	for(int i = 0; i < (int)u.size(); i++) {
		brn.push_back({u[i], v[i]});
	}
	int it = 0;
	while((int) tikrai.size() != n-1){
		pl.clear();
		form();
		int v = *virs.begin();
		dfs(v);
		int u = -1;
		for(int i = 0; i < n; i++) if(deg[i] == 1) u = i;
	//	cout << "komponentai: \n"; for(int i = 0; i < n; i++) cout << i << ": " << fP(i) << endl; cout << endl;
	//	cout << "suformuoju medi: \n"; for(int i = 0; i < pl.size(); i++) cout << brn[pl[i]].first << " - > " << brn[pl[i]].second << endl;
	//	cout << "\nmedzio lapas: " << u << endl;
	//	cout << endl;
		vector<int> rest;
		for(int i = 0; i < (int)pl.size(); i++){
			int a = fP(brn[pl[i]].first);
			int b = fP(brn[pl[i]].second);
			if(a == u || b == u){
				continue;
			}
			rest.push_back(pl[i]);
		}
		for(auto x : tikrai) rest.push_back(x);
		vector<pair<int, int> > aa;
		int mx = 0;
		for(auto x : gr[u]){ 
			rest.push_back(x.second);
			int cm = count_common_roads(rest);
			aa.push_back({cm, x.second});
			mx = max(mx, cm);
			rest.pop_back();
		}
		for(auto x : aa){
			if(x.first == mx) {
				tikrai.push_back(x.second);
				zn[x.second] = 1;
				conn(brn[x.second].first, brn[x.second].second);
		//		cout << brn[x.second].first << " -> " << brn[x.second].second << " tikrai geras" << endl;
			}else{
				zn[x.second] = 0;
		//		cout << brn[x.second].first << " -> " << brn[x.second].second << " tikrai blogas" << endl;
			}
		}
	}

	return tikrai;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:63:6: warning: unused variable 'it' [-Wunused-variable]
   63 |  int it = 0;
      |      ^~

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30