oj.uz

Submission #134640

# Submission time Handle Problem Language Result Execution time Memory
134640 2019-07-23T06:14:05 Z dvdg6566 Simurgh (IOI17_simurgh) C++14
30 / 100
 215 ms 3548 KB 
#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 300

int N,a,b;
vpi V[MAXN];
vpi edgeList;
vi res,cur;
vpi tmp;
int p[MAXN];
int lowlink[MAXN], depth[MAXN];
int par(int x){return (x==p[x])?x:p[x] = par(p[x]);}
vi bridges;

void dfs(int x,int p){
	// cout<<"DFS "<<x<<' '<<p<<'\n';
	lowlink[x] = depth[x];
	for (auto v : V[x])if(v.f!=p){
		if (depth[v.f] != -1){
			lowlink[x] = min(lowlink[x], lowlink[v.f]);
			continue;
		}
		depth[v.f] = depth[x]+1;
		dfs(v.f,x);
		lowlink[x] = min(lowlink[x], lowlink[v.f]);
	}
}

bool isBridge(int x, int y){
	if (lowlink[x]<=depth[y]&&depth[x]>depth[y])return 0;
	if (lowlink[y]<=depth[x]&&depth[y]>depth[x])return 0;
	// cout<<x<<' '<<y<<'\n';
	return 1;
}

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);
	}
	a=1;
	memset(depth,-1,sizeof(depth));
	depth[0]=0;
	dfs(0,0);
	// for (int i=0;i<N;++i)cout<<depth[i]<<' '<<lowlink[i]<<'\n';
	for (int i=0;i<SZ(u);++i){
		int a=edgeList[i].f;
		int b=edgeList[i].s;
		if (isBridge(a,b))bridges.pb(i);
	}

	for (auto i : bridges)res.pb(i);
	// for (auto i : bridges)cout<<i<<'\n';
	if (SZ(bridges) == N-1)return bridges;

	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 (auto it : bridges){
			cur.pb(it);
			p[par(edgeList[it].f)] = par(edgeList[it].s);
		}
		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);
		}
		if (SZ(cur) == N-1)continue;
		assert(SZ(cur) + 2 == N);
		for (auto x : V[i]){
			if (isBridge(i,x.f))continue;
			cur.pb(x.s);
			// for (auto i : cur)cout<<i<<' ' ;cout<<'\n';
			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 :tmp)cout<<x.f<<' '<<x.s<<'\n';
		// for (auto x:res)cout<<x<<' ';cout<<'\n';
	}
	sort(ALL(res));
	res.resize(unique(ALL(res)) - res.begin());
	// assert(SZ(res) == N-1);
	return res;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 376 KB correct
4 Correct 2 ms 256 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 2 ms 376 KB correct
7 Correct 2 ms 376 KB correct
8 Correct 3 ms 376 KB correct
9 Correct 2 ms 256 KB correct
10 Correct 2 ms 256 KB correct
11 Correct 2 ms 376 KB correct
12 Correct 2 ms 256 KB correct
13 Correct 2 ms 256 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 376 KB correct
4 Correct 2 ms 256 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 2 ms 376 KB correct
7 Correct 2 ms 376 KB correct
8 Correct 3 ms 376 KB correct
9 Correct 2 ms 256 KB correct
10 Correct 2 ms 256 KB correct
11 Correct 2 ms 376 KB correct
12 Correct 2 ms 256 KB correct
13 Correct 2 ms 256 KB correct
14 Correct 6 ms 376 KB correct
15 Correct 6 ms 376 KB correct
16 Correct 6 ms 348 KB correct
17 Correct 5 ms 456 KB correct
18 Correct 3 ms 376 KB correct
19 Correct 5 ms 376 KB correct
20 Correct 5 ms 308 KB correct
21 Correct 5 ms 376 KB correct
22 Correct 4 ms 376 KB correct
23 Correct 4 ms 376 KB correct
24 Correct 4 ms 376 KB correct
25 Correct 2 ms 376 KB correct
26 Correct 4 ms 376 KB correct
27 Correct 4 ms 348 KB correct
28 Correct 3 ms 376 KB correct
29 Correct 2 ms 376 KB correct
30 Correct 4 ms 376 KB correct
31 Correct 4 ms 376 KB correct
32 Correct 4 ms 376 KB correct
33 Correct 4 ms 376 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 376 KB correct
4 Correct 2 ms 256 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 2 ms 376 KB correct
7 Correct 2 ms 376 KB correct
8 Correct 3 ms 376 KB correct
9 Correct 2 ms 256 KB correct
10 Correct 2 ms 256 KB correct
11 Correct 2 ms 376 KB correct
12 Correct 2 ms 256 KB correct
13 Correct 2 ms 256 KB correct
14 Correct 6 ms 376 KB correct
15 Correct 6 ms 376 KB correct
16 Correct 6 ms 348 KB correct
17 Correct 5 ms 456 KB correct
18 Correct 3 ms 376 KB correct
19 Correct 5 ms 376 KB correct
20 Correct 5 ms 308 KB correct
21 Correct 5 ms 376 KB correct
22 Correct 4 ms 376 KB correct
23 Correct 4 ms 376 KB correct
24 Correct 4 ms 376 KB correct
25 Correct 2 ms 376 KB correct
26 Correct 4 ms 376 KB correct
27 Correct 4 ms 348 KB correct
28 Correct 3 ms 376 KB correct
29 Correct 2 ms 376 KB correct
30 Correct 4 ms 376 KB correct
31 Correct 4 ms 376 KB correct
32 Correct 4 ms 376 KB correct
33 Correct 4 ms 376 KB correct
34 Incorrect 215 ms 1804 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB correct
2 Correct 2 ms 376 KB correct
3 Runtime error 24 ms 3548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 376 KB correct
4 Correct 2 ms 256 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 2 ms 376 KB correct
7 Correct 2 ms 376 KB correct
8 Correct 3 ms 376 KB correct
9 Correct 2 ms 256 KB correct
10 Correct 2 ms 256 KB correct
11 Correct 2 ms 376 KB correct
12 Correct 2 ms 256 KB correct
13 Correct 2 ms 256 KB correct
14 Correct 6 ms 376 KB correct
15 Correct 6 ms 376 KB correct
16 Correct 6 ms 348 KB correct
17 Correct 5 ms 456 KB correct
18 Correct 3 ms 376 KB correct
19 Correct 5 ms 376 KB correct
20 Correct 5 ms 308 KB correct
21 Correct 5 ms 376 KB correct
22 Correct 4 ms 376 KB correct
23 Correct 4 ms 376 KB correct
24 Correct 4 ms 376 KB correct
25 Correct 2 ms 376 KB correct
26 Correct 4 ms 376 KB correct
27 Correct 4 ms 348 KB correct
28 Correct 3 ms 376 KB correct
29 Correct 2 ms 376 KB correct
30 Correct 4 ms 376 KB correct
31 Correct 4 ms 376 KB correct
32 Correct 4 ms 376 KB correct
33 Correct 4 ms 376 KB correct
34 Incorrect 215 ms 1804 KB WA in grader: NO
35 Halted 0 ms 0 KB -