oj.uz

Submission #240562

# Submission time Handle Problem Language Result Execution time Memory
240562 2020-06-20T02:41:26 Z arnold518 Rigged Roads (NOI19_riggedroads) C++14
100 / 100
 756 ms 126348 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;

int N, M;
pii EG[MAXN+10];
int A[MAXN+10];

vector<int> adj[MAXN+10];

int S[MAXN+10], E[MAXN+10], I[MAXN+10], cnt;
int par[MAXN+10], dep[MAXN+10], sz[MAXN+10], head[MAXN+10];

void dfs(int now, int bef, int d)
{
	par[now]=bef;
	dep[now]=d;
	sz[now]=1;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs(nxt, now, d+1);
		sz[now]+=sz[nxt];
	}
}

void hld(int now, int bef)
{
	S[now]=++cnt;
	I[S[now]]=now;

	int heavy=0;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		if(sz[heavy]<sz[nxt]) heavy=nxt;
	}
	if(heavy==0) return;

	head[heavy]=head[now];
	hld(heavy, now);

	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		if(nxt==heavy) continue;
		head[nxt]=nxt;
		hld(nxt, now);
	}

	E[now]=cnt;
}

int B[MAXN+10], ans[MAXN+10], num;
vector<int> tree[MAXN*4+10];

void init(int node, int tl, int tr)
{
	if(tl==tr)
	{
		tree[node].push_back(B[I[tl]]);
		return;
	}
	int mid=tl+tr>>1;
	init(node*2, tl, mid);
	init(node*2+1, mid+1, tr);
	for(auto it : tree[node*2]) tree[node].push_back(it);
	for(auto it : tree[node*2+1]) tree[node].push_back(it);
}

void query(int node, int tl, int tr, int l, int r, vector<int> &V)
{
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		while(!tree[node].empty())
		{
			if(ans[tree[node].back()]==0) V.push_back(tree[node].back());
			tree[node].pop_back();
		}
		return;
	}
	int mid=tl+tr>>1;
	query(node*2, tl, mid, l, r, V);
	query(node*2+1, mid+1, tr, l, r, V);
}

void query(int u, int v)
{
	vector<int> V;
	while(head[u]!=head[v])
	{
		if(dep[head[u]]>dep[head[v]]) swap(u, v);
		query(1, 1, N, S[head[v]], S[v], V);
		v=par[head[v]];
	}
	if(dep[u]>dep[v]) swap(u, v);
	if(u!=v) query(1, 1, N, S[u]+1, S[v], V);
	sort(V.begin(), V.end());

	for(auto it : V) ans[it]=++num;
}

int main()
{
	int i, j;

	scanf("%d%d", &N, &M);
	for(i=1; i<=M; i++) scanf("%d%d", &EG[i].first, &EG[i].second);
	for(i=1; i<N; i++)
	{
		int t; scanf("%d", &t); A[t]=1;
		adj[EG[t].first].push_back(EG[t].second);
		adj[EG[t].second].push_back(EG[t].first);
	}

	dfs(1, 1, 1);
	head[1]=1;
	hld(1, 1);

	for(i=1; i<=M; i++)
	{
		if(!A[i]) continue;
		int u=EG[i].first, v=EG[i].second;
		if(dep[u]>dep[v]) swap(u, v);
		B[v]=i;
	}

	
	init(1, 1, N);
	for(i=1; i<=M; i++)
	{
		if(A[i])
		{
			if(!ans[i]) ans[i]=++num;
		}
		else
		{
			int u=EG[i].first, v=EG[i].second;
			query(u, v);
			ans[i]=++num;
		}
	}
	for(i=1; i<=M; i++) printf("%d ", ans[i]);
}

Compilation message

riggedroads.cpp: In function 'void init(int, int, int)':
riggedroads.cpp:69:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
riggedroads.cpp: In function 'void query(int, int, int, int, int, std::vector<int>&)':
riggedroads.cpp:88:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
riggedroads.cpp: In function 'int main()':
riggedroads.cpp:111:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
riggedroads.cpp:113:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
riggedroads.cpp:114:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=M; i++) scanf("%d%d", &EG[i].first, &EG[i].second);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:117:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int t; scanf("%d", &t); A[t]=1;
          ~~~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 35712 KB Output is correct
2 Correct 25 ms 35712 KB Output is correct
3 Correct 26 ms 35712 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 35712 KB Output is correct
2 Correct 25 ms 35712 KB Output is correct
3 Correct 26 ms 35712 KB Output is correct
4 Correct 25 ms 35712 KB Output is correct
5 Correct 25 ms 35840 KB Output is correct
6 Correct 24 ms 35744 KB Output is correct
7 Correct 24 ms 35712 KB Output is correct
8 Correct 24 ms 35712 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 58736 KB Output is correct
2 Correct 250 ms 66000 KB Output is correct
3 Correct 233 ms 48636 KB Output is correct
4 Correct 332 ms 105704 KB Output is correct
5 Correct 368 ms 109284 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 69756 KB Output is correct
2 Correct 134 ms 49908 KB Output is correct
3 Correct 77 ms 43000 KB Output is correct
4 Correct 160 ms 61864 KB Output is correct
5 Correct 71 ms 45304 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 103104 KB Output is correct
2 Correct 475 ms 111240 KB Output is correct
3 Correct 158 ms 58480 KB Output is correct
4 Correct 178 ms 67696 KB Output is correct
5 Correct 579 ms 126348 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 84764 KB Output is correct
2 Correct 221 ms 67452 KB Output is correct
3 Correct 660 ms 112232 KB Output is correct
4 Correct 526 ms 101356 KB Output is correct
5 Correct 54 ms 41720 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 35712 KB Output is correct
2 Correct 25 ms 35712 KB Output is correct
3 Correct 26 ms 35712 KB Output is correct
4 Correct 25 ms 35712 KB Output is correct
5 Correct 25 ms 35840 KB Output is correct
6 Correct 24 ms 35744 KB Output is correct
7 Correct 24 ms 35712 KB Output is correct
8 Correct 24 ms 35712 KB Output is correct
9 Correct 133 ms 58736 KB Output is correct
10 Correct 250 ms 66000 KB Output is correct
11 Correct 233 ms 48636 KB Output is correct
12 Correct 332 ms 105704 KB Output is correct
13 Correct 368 ms 109284 KB Output is correct
14 Correct 221 ms 69756 KB Output is correct
15 Correct 134 ms 49908 KB Output is correct
16 Correct 77 ms 43000 KB Output is correct
17 Correct 160 ms 61864 KB Output is correct
18 Correct 71 ms 45304 KB Output is correct
19 Correct 433 ms 103104 KB Output is correct
20 Correct 475 ms 111240 KB Output is correct
21 Correct 158 ms 58480 KB Output is correct
22 Correct 178 ms 67696 KB Output is correct
23 Correct 579 ms 126348 KB Output is correct
24 Correct 333 ms 84764 KB Output is correct
25 Correct 221 ms 67452 KB Output is correct
26 Correct 660 ms 112232 KB Output is correct
27 Correct 526 ms 101356 KB Output is correct
28 Correct 54 ms 41720 KB Output is correct
29 Correct 634 ms 99564 KB Output is correct
30 Correct 756 ms 101612 KB Output is correct
31 Correct 718 ms 107452 KB Output is correct
32 Correct 247 ms 49016 KB Output is correct
33 Correct 562 ms 108020 KB Output is correct