제출 #58682

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58682		reality	Simurgh (IOI17_simurgh)	C++17	0 / 100	3 ms	488 KiB

simurgh

#include "simurgh.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 512;
int f[N];
int was[N * N];
int get(int k) {
	return k == f[k] ? k : f[k] = get(f[k]);
}
map < vi , int > w;
int get(vi E) {
	return count_common_roads(E);
}
vi find_roads(int n,vi u,vi v) {
	int m = u.size();
	vi answer;
	for (int k = 0;k < m;++k) {
		for (int i = 0;i < n;++i)
			f[i] = i;
		vi e;
		for (int i = 0;i < m;++i) 
			if (i != k) {
				if (get(u[i]) != get(v[i]))
					f[get(u[i])] = get(v[i]),e.pb(i);
			}
		for (int i = 0;i < n;++i)
			f[i] = i;
		vi ee;
		f[get(u[k])] = get(f[v[k]]);
		ee.pb(k);
		for (auto it : e)
			if (get(u[it]) != get(v[it])) {
				f[get(u[it])] = get(v[it]);
				ee.pb(it);
			}
		for (int i = 0;i < m;++i) {
			if (get(u[i]) != get(v[i]))
				f[get(u[i])] = get(v[i]),ee.pb(i);
		}
		int cnt;
		if (!w.count(ee))
			w[ee] = get(ee);
		cnt = w[ee];
		int cur = get(e);
		if (cur >= cnt)
			was[k] = 1;
	}
	for (int i = 0;i < m;++i)
		if (!was[i])
			answer.pb(i);
	return answer;
}

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