Submission #790660

#	Time	Username	Problem	Language	Result	Execution time	Memory
790660		PoonYaPat	Simurgh (IOI17_simurgh)	C++14	0 / 100	114 ms	5296 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

struct Edge {
	int a,idx,mode;
};

int n,m,deg[505];
vector<pii> edge;
priority_queue<pii> pq; //deg, node
vector<Edge> adj[505];
bool fin[505],ans[250010];

int p[505],r[505];

void reset() {
	for (int i=0; i<n; ++i) p[i]=i, r[i]=1;
}

int find(int x) {
	while (x!=p[x]) x=p[x];
	return x; 
} 

void unite(int x, int y) {
	x=find(x); y=find(y);
	if (r[x]<r[y]) swap(x,y);
	p[y]=x;
	if (r[x]==r[y]) ++r[x];
}

void solve1(int x) {
	vector<pii> temp; //val,idx
	vector<int> v;
	int ma=0;
	reset();

	for (int i=0; i<m; ++i) {
		if (edge[i].first==x || edge[i].second==x) continue;
		if (find(edge[i].first)!=find(edge[i].second)) {
			unite(edge[i].first,edge[i].second);
			v.push_back(i);
		}
	}

	for (auto s : adj[x]) {
		v.push_back(s.idx);
		int h=count_common_roads(v);
		ma=max(h,ma);
		temp.push_back(pii(h,s.idx));
		v.pop_back();
	}

	for (auto s : temp) if (s.first==ma) ans[s.second]=true;
}


vector<int> find_roads(int N, vector<int> u, vector<int> v) {
	n=N;
	m=u.size();
	for (int i=0; i<m; ++i) {
		edge.push_back(pii(u[i],v[i]));
		adj[u[i]].push_back({v[i],i,-1});
		adj[v[i]].push_back({u[i],i,-1});
		++deg[u[i]];
		++deg[v[i]];
	}

	int ma=0, st;
	for (int i=0; i<n; ++i) if (deg[i]>ma) ma=deg[i], st=i;

	for (int i=0; i<n; ++i) solve1(i);
	vector<int> Ans;
	for (int i=0; i<m; ++i) if (ans[i]) Ans.push_back(i);
	return Ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:71:12: warning: variable 'st' set but not used [-Wunused-but-set-variable]
   71 |  int ma=0, st;
      |            ^~

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