Submission #240562

#	Time	Username	Problem	Language	Result	Execution time	Memory
240562		arnold518	Rigged Roads (NOI19_riggedroads)	C++14	100 / 100	756 ms	126348 KiB

riggedroads

#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 (stderr)

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 / 8
• Subtask 2: 19 / 19
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 32 / 32