oj.uz

Submission #299795

# Submission time Handle Problem Language Result Execution time Memory
299795 2020-09-15T16:34:27 Z errorgorn Simurgh (IOI17_simurgh) C++14
30 / 100
 207 ms 3584 KB 
#include "simurgh.h"

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

#define ll long long
#define ii pair<int,int>
#define fi first
#define se second

#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

ii mp(int i,int j){
	if (i<j) return ii(i,j);
	else return ii(j,i);
}

int n,m;
ii edges[300005];
vector<ii> al[255];

bool bridge[300005];
bool good[300005];

int in[300005];
int low[300005];

int TIME=1;
void dfs(int i,int p){
	in[i]=low[i]=TIME++;
	
	for (auto &it:al[i]){
		if (!in[it.fi]){
			dfs(it.fi,i);
			low[i]=min(low[i],low[it.fi]);
			
			if (in[i]<low[it.fi]){
				bridge[it.se]=true;
			}
		}
		else if (it.fi!=p){
			low[i]=min(low[i],in[it.fi]);
		}
	}
}

struct UFDS{
	int p[255];
	
	void reset(){
		rep(x,0,255) p[x]=x;
	}
	
	int parent(int i){
		if (p[i]==i) return i;
		else return p[i]=parent(p[i]);
	}
	
	bool unions(int i,int j){
		i=parent(i),j=parent(j);
		
		if (i==j) return false;
		p[i]=j;
		return true;
	}
	
} ufds;

std::vector<int> find_roads(int N, std::vector<int> u, std::vector<int> v) {
	n=N,m=sz(u);
	
	rep(x,0,m){
		edges[x]=ii(u[x],v[x]);
		al[u[x]].push_back(ii(v[x],x));
		al[v[x]].push_back(ii(u[x],x));
	}
	
	//dfs(0,-1);
	
	rep(node,0,n){
		ufds.reset();
		
		vector<ii> child;
		
		for (auto &it:al[node]) child.push_back(it);
		
		vector<int> cand;
		rep(x,0,m){
			if (edges[x].fi==node || edges[x].se==node) continue;
			
			if (ufds.unions(edges[x].fi,edges[x].se)){
				cand.push_back(x);
			}
		}
		
		map<int,vector<int> > neigh;
		
		for (auto &it:child){
			int temp=ufds.parent(it.fi);
			
			if (!neigh.count(temp)) neigh[temp]=vector<int>();
			neigh[temp].push_back(it.se);
		}
		
		for (auto &it:neigh){
			vector<int> cand2=cand;
			
			for (auto &it2:neigh) if (it2!=it){
				cand2.push_back(it2.se[0]);
			}
			
			int val=-1;
			vector<int> proc;
			
			for (auto &iter:it.se){
				cand2.push_back(iter);
				
				int temp=count_common_roads(cand2);
				if (temp>val) val=temp,proc.clear();
				if (temp==val) proc.push_back(iter);
				
				cand2.pop_back();
			}
			
			for (auto &it:proc) good[it]=true;
		}
	}
	
	vector<int> ans;
	rep(x,0,300005) if (good[x]) ans.push_back(x);
	return ans;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB correct
2 Correct 2 ms 384 KB correct
3 Correct 2 ms 384 KB correct
4 Correct 2 ms 384 KB correct
5 Correct 2 ms 384 KB correct
6 Correct 2 ms 384 KB correct
7 Correct 2 ms 384 KB correct
8 Correct 2 ms 384 KB correct
9 Correct 2 ms 384 KB correct
10 Correct 2 ms 384 KB correct
11 Correct 2 ms 384 KB correct
12 Correct 2 ms 384 KB correct
13 Correct 2 ms 384 KB correct
14 Correct 5 ms 384 KB correct
15 Correct 5 ms 384 KB correct
16 Correct 5 ms 384 KB correct
17 Correct 5 ms 384 KB correct
18 Correct 3 ms 384 KB correct
19 Correct 5 ms 384 KB correct
20 Correct 5 ms 384 KB correct
21 Correct 4 ms 512 KB correct
22 Correct 4 ms 384 KB correct
23 Correct 4 ms 384 KB correct
24 Correct 3 ms 384 KB correct
25 Correct 2 ms 384 KB correct
26 Correct 3 ms 384 KB correct
27 Correct 4 ms 384 KB correct
28 Correct 2 ms 384 KB correct
29 Correct 2 ms 384 KB correct
30 Correct 4 ms 384 KB correct
31 Correct 3 ms 512 KB correct
32 Correct 4 ms 384 KB correct
33 Correct 4 ms 384 KB correct
34 Incorrect 207 ms 1792 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 384 KB correct
2 Correct 2 ms 384 KB correct
3 Runtime error 21 ms 3584 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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