oj.uz

Submission #805708

# Submission time Handle Problem Language Result Execution time Memory
805708 2023-08-03T21:04:03 Z Username4132 Simurgh (IOI17_simurgh) C++14
30 / 100
 95 ms 4384 KB 
#include "simurgh.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<cassert>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second

int n, m, tm, base, esp[125010], pv[510], pe[510], tin[510];
bool vis[510];
pii edges[125010];
vector<int> ted;
vector<vector<int>> uns;
vector<pii> g[510];

void dfs(int v){
	tin[v]=tm++;
	vis[v]=true;
	for(pii to:g[v]) if(!vis[to.F]){
		pv[to.F]=v;
		pe[to.F]=to.S;
		ted.PB(to.S);
		dfs(to.F);
	}
}

int add_count(int r){
	int cou=base;
	vector<int> ask;
	forn(i, r){
		if(!uns[i].empty()) ask.PB(uns[i].back()), cou-=esp[ted[i]];
		else ask.PB(ted[i]);
	}
	forsn(i, r, n-1) ask.PB(ted[i]);
	return count_common_roads(ask) - cou;
}

void dfs2(int l, int r, int lv, int rv){
	if(lv==rv) return;
	if(r-l==1){
		esp[uns[l].back()]=1;
		return;
	}
	int mid = (l+r)>>1, value = add_count(mid);
	dfs2(l, mid, lv, value);
	dfs2(mid, r, value, rv);
}

vector<int> find_roads(int N, vector<int> u, vector<int> v) {
	n=N; m=u.size();
	forn(i, m){
		g[u[i]].PB({v[i], i});
		g[v[i]].PB({u[i], i});
		edges[i]={u[i], v[i]};
		esp[i]=-1;
	}
	dfs(0);
	sort(ted.begin(), ted.end());
	base = count_common_roads(ted);
	uns.resize(ted.size());

	forn(i, m){
		int a = edges[i].F, b = edges[i].S, know=-1;
		if(tin[a]<tin[b]) swap(a, b);
		if(pv[a]==b) continue;
		uns[lower_bound(ted.begin(), ted.end(), pe[a]) - ted.begin()].PB(i);
		vector<int> ed, res;
		int cur=a;
		while(cur!=b){
			int e = pe[cur];
			if(esp[e]!=-1) know=e;
			else{
				vector<int> tmp;
				for(int el:ted) if(el!=e) tmp.PB(el);
				tmp.PB(i);
				ed.PB(e);
				res.PB(count_common_roads(tmp));
			}
			cur = pv[cur];
		}
		if(know==-1){
			int mx = *max_element(res.begin(), res.end());
			mx = max(mx, base);
			forn(j, ed.size()) esp[ed[j]]=(res[j]!=mx);
		}
		else{
			vector<int> tmp;
			for(int el:ted) if(el!=know) tmp.PB(el);
			tmp.PB(i);
			int value = count_common_roads(tmp);
			forn(j, ed.size()) esp[ed[j]]=esp[know]^(res[j]!=value);
		}
	}
	for(int e:ted) if(esp[e]==-1) esp[e]=1;
	bool cont=true;
	while(cont){
		int rv = add_count(n-1);
		dfs2(0, n-1, 0, rv);
		cont=false;
		forn(i, n-1){
			if(!uns[i].empty()) uns[i].pop_back();
			cont|=!uns[i].empty();
		}
	}

	vector<int> ret;
	forn(i, m) if(esp[i]==1) ret.PB(i);
	assert((int)ret.size()==n-1);
	return ret;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Incorrect 70 ms 4384 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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