제출 #51835

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51835		ernestvw	Simurgh (IOI17_simurgh)	C++11	13 / 100	3064 ms	844 KiB

simurgh

#include <bits/stdc++.h>
using namespace std;

#include "simurgh.h"
//int count_common_roads(vector<int> r);

struct Arc {
	int u, v, i;
};

int nbNodes, nbArcs;
vector<Arc> arcs;
vector<Arc> adj[501];
map<pair<int, int>, int> idx;

vector<int> sol, cur;
bool found = 0;

int parent[501];
int f(int x){return parent[x]==x?x:(parent[x]=f(parent[x]));}
void m(int x, int y){parent[f(x)]=f(y);}

bool ok() {
	if((int)cur.size()!=nbNodes-1)return false;
	for(int i = 0; i < nbNodes; i++) parent[i] = i;
	for(int i : cur)
		if(f(arcs[i].u) != f(arcs[i].v)) m(arcs[i].u, arcs[i].v);
	int l=-1;
	for(int i = 0; i < nbNodes; i++){
		if(f(i) != l) {
			if(l == -1) l = f(i);
			else return false;
		}
	}
	return true;
}

void find(int i) {
	if(i == nbArcs) {
		if(ok() and count_common_roads(cur) == nbNodes - 1) {
			sol = cur;
			found = true;
		}
		return;
	}
	if(found) return;
	if((int)cur.size() < nbNodes - 1) {
		cur.push_back(i);
		find(i + 1);
		cur.pop_back();
	}
	find(i + 1);
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	nbNodes = n;
	nbArcs = (int)u.size();
	arcs.clear();
	for(int i = 0; i < nbArcs; i++) {
		arcs.push_back({u[i], v[i], i});
		adj[u[i]].push_back({u[i], v[i], i});
		adj[v[i]].push_back({v[i], u[i], i});
	}
	find(0);
	return sol;
}
/*
bool GOLDEN[501*250];
int count_common_roads(vector<int> r) {
	int cnt(0);
	for(int i:r)if(GOLDEN[i])cnt++;
	return cnt;
}

int main() {
	int T=1;
	while(T--){
	int n, m;cin>>n>>m;
	vector<int>u(m), v(m);
	for(int i=0;i<m;i++){
		cin>>u[i]>>v[i];
	}
	for(int i=0;i<m;i++)GOLDEN[i]=0;
	for(int i=0;i<n-1;i++){int s;cin>>s;GOLDEN[s]=1;}
	vector<int> sol = find_roads(n, u, v);
	for(int i : sol) {
		cout << i << " ";
	}
	cout << endl;
	}
}
*/

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