oj.uz

Submission #51835

# Submission time Handle Problem Language Result Execution time Memory
51835 2018-06-21T13:43:16 Z ernestvw Simurgh (IOI17_simurgh) C++11
13 / 100
 3000 ms 844 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 376 KB correct
2 Correct 6 ms 376 KB correct
3 Correct 11 ms 528 KB correct
4 Correct 2 ms 528 KB correct
5 Correct 2 ms 632 KB correct
6 Correct 3 ms 636 KB correct
7 Correct 2 ms 640 KB correct
8 Correct 2 ms 660 KB correct
9 Correct 2 ms 708 KB correct
10 Correct 3 ms 844 KB correct
11 Correct 2 ms 844 KB correct
12 Correct 2 ms 844 KB correct
13 Correct 10 ms 844 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 376 KB correct
2 Correct 6 ms 376 KB correct
3 Correct 11 ms 528 KB correct
4 Correct 2 ms 528 KB correct
5 Correct 2 ms 632 KB correct
6 Correct 3 ms 636 KB correct
7 Correct 2 ms 640 KB correct
8 Correct 2 ms 660 KB correct
9 Correct 2 ms 708 KB correct
10 Correct 3 ms 844 KB correct
11 Correct 2 ms 844 KB correct
12 Correct 2 ms 844 KB correct
13 Correct 10 ms 844 KB correct
14 Execution timed out 3064 ms 844 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 376 KB correct
2 Correct 6 ms 376 KB correct
3 Correct 11 ms 528 KB correct
4 Correct 2 ms 528 KB correct
5 Correct 2 ms 632 KB correct
6 Correct 3 ms 636 KB correct
7 Correct 2 ms 640 KB correct
8 Correct 2 ms 660 KB correct
9 Correct 2 ms 708 KB correct
10 Correct 3 ms 844 KB correct
11 Correct 2 ms 844 KB correct
12 Correct 2 ms 844 KB correct
13 Correct 10 ms 844 KB correct
14 Execution timed out 3064 ms 844 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 844 KB correct
2 Incorrect 59 ms 844 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 376 KB correct
2 Correct 6 ms 376 KB correct
3 Correct 11 ms 528 KB correct
4 Correct 2 ms 528 KB correct
5 Correct 2 ms 632 KB correct
6 Correct 3 ms 636 KB correct
7 Correct 2 ms 640 KB correct
8 Correct 2 ms 660 KB correct
9 Correct 2 ms 708 KB correct
10 Correct 3 ms 844 KB correct
11 Correct 2 ms 844 KB correct
12 Correct 2 ms 844 KB correct
13 Correct 10 ms 844 KB correct
14 Execution timed out 3064 ms 844 KB Time limit exceeded
15 Halted 0 ms 0 KB -