Submission #804421

#	Time	Username	Problem	Language	Result	Execution time	Memory
804421		ngrace	Simurgh (IOI17_simurgh)	C++14	51 / 100	113 ms	3448 KiB

simurgh

#include "simurgh.h"

//could probs be optimised to not tle on sub3

#include <bits/stdc++.h>
using namespace std;
#define ve vector
#define ll long long
#define ii pair<int, int>
#define fi first
#define se second

int N;
set<int> ans;
int edgeInd[240][240];

struct DSU{
	int par[500];
	int si=0;
	DSU(int siz){
		si=siz;
		reset();
	}
	void reset(){
		for(int i=0; i<si; i++) par[i]=i;
	}
	int root(int x) {
		return (x==par[x]) ? x : par[x]=root(par[x]);
	}
	void doUnion(int a, int b){
		par[root(a)]=root(b);
	}
};



std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	N = n;

	if(n==2){
		ve<int> res = {0};
		return res;
	}

	for(int i=0; i<240; i++){
		for(int j=0; j<240; j++){
			edgeInd[i][j] = -1;
		}
	}
	for(int i=0; i < u.size(); i++){
		edgeInd[u[i]][v[i]] = i;
		edgeInd[v[i]][u[i]] = i;
	}

	ve<ve<bool>> known(N, ve<bool>(N, false));
	for(int i=0; i<N; i++){
		ve<int> tree;
		DSU comp(N);
		for(int a=0; a<N; a++){
			if(a==i) continue;
			for(int b=a+1; b<N; b++){
				if(b==i || edgeInd[a][b]==-1) continue;
				if(comp.root(a)==comp.root(b)) continue;
				tree.push_back(edgeInd[a][b]);
				comp.doUnion(a, b);
			}
		}
		set<int> comps;
		for(int a=0; a<N; a++){
			if(a==i) continue;
			comps.insert(comp.root(a));
		}
		ve<ve<int>> compGroups;
		for(int a:comps){
			compGroups.push_back({});
			for(int b=0; b<N; b++){
				if(comp.root(a)==comp.root(b) && edgeInd[i][b]!=-1) compGroups.back().push_back(b);
			}
		}

		for(int j=0; j<compGroups.size(); j++){
			for(int tmp=0; tmp<compGroups.size(); tmp++){
				if(tmp==j) continue;
				tree.push_back(edgeInd[i][compGroups[tmp][0]]);
			}
			int ma=0;
			ve<int> cou(N, -1);
			bool first=true;
			for(int node:compGroups[j]){
				if(known[i][node]){
					cou[node] = -1;
					if(ans.find(edgeInd[i][node])==ans.end() || !first) continue;
					first=false;
				}
				tree.push_back(edgeInd[i][node]);
				cou[node] = count_common_roads(tree);
				ma = max(ma, cou[node]);
				tree.pop_back();
				known[i][node] = known[node][i] = true;
			}
			
			for(int node:compGroups[j]){
				if(cou[node]<ma) continue;
				//cout<<"Edge from "<<i<<" to "<<node<<endl;
				ans.insert(edgeInd[i][node]);
			}

			for(int tmp=0; tmp<compGroups.size()-1; tmp++) tree.pop_back();
		}
	}

	ve<int> res;
	for(int i:ans) res.push_back(i);
	return res;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:50:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i=0; i < u.size(); i++){
      |               ~~^~~~~~~~~~
simurgh.cpp:81:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   for(int j=0; j<compGroups.size(); j++){
      |                ~^~~~~~~~~~~~~~~~~~
simurgh.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |    for(int tmp=0; tmp<compGroups.size(); tmp++){
      |                   ~~~^~~~~~~~~~~~~~~~~~
simurgh.cpp:108:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |    for(int tmp=0; tmp<compGroups.size()-1; tmp++) tree.pop_back();
      |                   ~~~^~~~~~~~~~~~~~~~~~~~

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