답안 #134602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
134602	2019-07-23T05:21:03 Z	dvdg6566	Simurgh (IOI17_simurgh)	C++14	0 / 100	22 ms	3576 KB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
#define pb emplace_back
#define mp make_pair
#define f first
#define s second
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define MAXN 241

int N,a,b;
vpi V[MAXN];
vpi edgeList;
vi res,cur;
vpi tmp;
int p[MAXN];

int par(int x){return (x==p[x])?x:p[x] = par(p[x]);}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	N=n;
	for (int i=0;i<SZ(u);++i){
		a=u[i];b=v[i];
		V[a].pb(b,i);V[b].pb(a,i);
		edgeList.pb(a,b);
	}
	for (int i=0;i<N;++i){
		// We want to find all edges with index to a bigger node
		for (int j=0;j<N;++j)p[j]=j;
		cur.clear();
		tmp.clear();
		for (int j=0;j<SZ(edgeList);++j){
			pi it = edgeList[j];
			if (it.f == i || it.s == i)continue;
			if (par(it.f) == par(it.s))continue;
			p[par(it.f)] = par(it.s);
			cur.pb(j);
		}
		// cout<<SZ(cur)<<'\n';
		for (auto x : V[i]){
			cur.pb(x.s);
			int t = count_common_roads(cur);
			tmp.pb(x.s,t);
			cur.pop_back();
		}
		int lowest = 1e9;
		for (auto x : tmp)lowest = min(lowest,x.s);
		for (auto x : tmp){
			if (x.s > lowest)res.pb(x.f);
		}
		int hh = 0;
		for (auto x :tmp)hh=max(hh,x.s);
		if (hh == lowest){
			for (auto x:tmp)res.pb(x.f);
		}
		// for (auto x:res)cout<<x<<' ';cout<<'\n';
	}
	sort(ALL(res));
	res.resize(unique(ALL(res)) - res.begin());

	return res;
}

Subtask #1

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	correct
2	Correct	2 ms	256 KB	correct
3	Correct	2 ms	256 KB	correct
4	Correct	2 ms	376 KB	correct
5	Correct	2 ms	256 KB	correct
6	Correct	2 ms	380 KB	correct
7	Correct	2 ms	256 KB	correct
8	Correct	2 ms	504 KB	correct
9	Incorrect	2 ms	256 KB	WA in grader: NO
10	Halted	0 ms	0 KB	-

Subtask #2

0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	correct
2	Correct	2 ms	256 KB	correct
3	Correct	2 ms	256 KB	correct
4	Correct	2 ms	376 KB	correct
5	Correct	2 ms	256 KB	correct
6	Correct	2 ms	380 KB	correct
7	Correct	2 ms	256 KB	correct
8	Correct	2 ms	504 KB	correct
9	Incorrect	2 ms	256 KB	WA in grader: NO
10	Halted	0 ms	0 KB	-

Subtask #3

0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	correct
2	Correct	2 ms	256 KB	correct
3	Correct	2 ms	256 KB	correct
4	Correct	2 ms	376 KB	correct
5	Correct	2 ms	256 KB	correct
6	Correct	2 ms	380 KB	correct
7	Correct	2 ms	256 KB	correct
8	Correct	2 ms	504 KB	correct
9	Incorrect	2 ms	256 KB	WA in grader: NO
10	Halted	0 ms	0 KB	-

Subtask #4

0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	correct
2	Correct	2 ms	256 KB	correct
3	Runtime error	22 ms	3576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Halted	0 ms	0 KB	-

Subtask #5

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	correct
2	Correct	2 ms	256 KB	correct
3	Correct	2 ms	256 KB	correct
4	Correct	2 ms	376 KB	correct
5	Correct	2 ms	256 KB	correct
6	Correct	2 ms	380 KB	correct
7	Correct	2 ms	256 KB	correct
8	Correct	2 ms	504 KB	correct
9	Incorrect	2 ms	256 KB	WA in grader: NO
10	Halted	0 ms	0 KB	-