oj.uz

Submission #242846

# Submission time Handle Problem Language Result Execution time Memory
242846 2020-06-29T11:40:13 Z moonrabbit2 Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 548 ms 71432 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int> tii;
typedef tuple<ll,ll,ll> tll;
typedef tuple<int,int,int,int> ti4;
typedef vector<vector<ll>> mat;
const ll mod=1e9+7,inf=1e18;
const int N=3e5+5,M=2e5+5,K=1e7+5;
int n,m,u[N],v[N],r[N],ok[N],cnt,ans[N];
vector<pll> g[N];
int in[N],pe[N],h[N],par[19][N],curp[N];
vector<int> V;
int clr(int u,int v){
	if(!u||h[u]<=h[v]) return u;
	if(!in[pe[u]]) V.emplace_back(pe[u]);
	in[pe[u]]=1;
	return curp[u]=clr(curp[u],v);
}
void dfs(int u){
	for(auto [v,d] : g[u]) if(v!=par[0][u]){
		h[v]=h[u]+1; par[0][v]=u; curp[v]=u; pe[v]=d; dfs(v);
	}
}
int lca(int u,int v){
	if(h[u]>h[v]) swap(u,v);
	for(int bit=18;bit>=0;bit--) if((h[v]-h[u])&(1<<bit)){
		v=par[bit][v];
	}
	if(u==v) return u;
	for(int bit=18;bit>=0;bit--) if(par[bit][u]!=par[bit][v]){
		u=par[bit][u]; v=par[bit][v];
	}
	return par[0][u];
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>u[i]>>v[i];
	for(int i=1;i<n;i++){
		cin>>r[i];
		ok[r[i]]=1;
		g[u[r[i]]].emplace_back(v[r[i]],r[i]);
		g[v[r[i]]].emplace_back(u[r[i]],r[i]);
	}
	h[1]=1; dfs(1); in[0]=1;
	for(int bit=1;bit<19;bit++) for(int i=1;i<=n;i++){
		par[bit][i]=par[bit-1][par[bit-1][i]];
	}
	for(int i=1;i<=m;i++){
		if(ans[i]){
			cout<<ans[i]<<" "; continue;
		}
		if(ok[i]){
			in[i]=1; cout<<++cnt<<" "; continue;
		}
		int uv=lca(u[i],v[i]);
		clr(u[i],uv); clr(v[i],uv);
		sort(V.begin(),V.end());
		for(auto j : V) ans[j]=++cnt;
		V.clear();
		cout<<++cnt<<" ";
	}
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7552 KB Output is correct
2 Correct 9 ms 7552 KB Output is correct
3 Correct 9 ms 7680 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7552 KB Output is correct
2 Correct 9 ms 7552 KB Output is correct
3 Correct 9 ms 7680 KB Output is correct
4 Correct 9 ms 7680 KB Output is correct
5 Correct 11 ms 7808 KB Output is correct
6 Correct 10 ms 7808 KB Output is correct
7 Correct 10 ms 7680 KB Output is correct
8 Correct 12 ms 7680 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 25060 KB Output is correct
2 Correct 178 ms 32656 KB Output is correct
3 Correct 135 ms 20464 KB Output is correct
4 Correct 187 ms 55888 KB Output is correct
5 Correct 215 ms 58288 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 33216 KB Output is correct
2 Correct 94 ms 18912 KB Output is correct
3 Correct 47 ms 13484 KB Output is correct
4 Correct 120 ms 26540 KB Output is correct
5 Correct 36 ms 15272 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 59500 KB Output is correct
2 Correct 395 ms 66336 KB Output is correct
3 Correct 76 ms 24080 KB Output is correct
4 Correct 126 ms 32096 KB Output is correct
5 Correct 415 ms 71432 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 42804 KB Output is correct
2 Correct 159 ms 31812 KB Output is correct
3 Correct 461 ms 62944 KB Output is correct
4 Correct 417 ms 58884 KB Output is correct
5 Correct 30 ms 12416 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7552 KB Output is correct
2 Correct 9 ms 7552 KB Output is correct
3 Correct 9 ms 7680 KB Output is correct
4 Correct 9 ms 7680 KB Output is correct
5 Correct 11 ms 7808 KB Output is correct
6 Correct 10 ms 7808 KB Output is correct
7 Correct 10 ms 7680 KB Output is correct
8 Correct 12 ms 7680 KB Output is correct
9 Correct 76 ms 25060 KB Output is correct
10 Correct 178 ms 32656 KB Output is correct
11 Correct 135 ms 20464 KB Output is correct
12 Correct 187 ms 55888 KB Output is correct
13 Correct 215 ms 58288 KB Output is correct
14 Correct 156 ms 33216 KB Output is correct
15 Correct 94 ms 18912 KB Output is correct
16 Correct 47 ms 13484 KB Output is correct
17 Correct 120 ms 26540 KB Output is correct
18 Correct 36 ms 15272 KB Output is correct
19 Correct 394 ms 59500 KB Output is correct
20 Correct 395 ms 66336 KB Output is correct
21 Correct 76 ms 24080 KB Output is correct
22 Correct 126 ms 32096 KB Output is correct
23 Correct 415 ms 71432 KB Output is correct
24 Correct 233 ms 42804 KB Output is correct
25 Correct 159 ms 31812 KB Output is correct
26 Correct 461 ms 62944 KB Output is correct
27 Correct 417 ms 58884 KB Output is correct
28 Correct 30 ms 12416 KB Output is correct
29 Correct 531 ms 58136 KB Output is correct
30 Correct 548 ms 60968 KB Output is correct
31 Correct 488 ms 59636 KB Output is correct
32 Correct 163 ms 20344 KB Output is correct
33 Correct 419 ms 60024 KB Output is correct