oj.uz

Submission #901549

# Submission time Handle Problem Language Result Execution time Memory
901549 2024-01-09T14:21:15 Z pcc Rigged Roads (NOI19_riggedroads) C++14
100 / 100
 1232 ms 232904 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 3e5+10;
pii edges[mxn];
int N,M;
int head[mxn*60],pre[mxn*60],to[mxn*60];
int tpp;
int ppp;
bitset<mxn> need;

int newnode(){
	return ++ppp;
}

void ADDEDGE(int a,int b){
	tpp++;
	assert(tpp<mxn*60);
	pre[tpp] = head[a];
	head[a] = tpp;
	to[tpp] = b;
	return;
}


namespace TREE{

vector<pii> tree[mxn];
int par[mxn][20],vid[mxn][20],dep[mxn];

void dfs(int now){
	for(int i = 1;i<20;i++){
		par[now][i] = par[par[now][i-1]][i-1];
		vid[now][i] = newnode();
		ADDEDGE(vid[now][i],vid[now][i-1]);
		ADDEDGE(vid[now][i],vid[par[now][i-1]][i-1]);
	}
	for(auto nxt:tree[now]){
		if(nxt.fs == par[now][0])continue;
		par[nxt.fs][0] = now;
		vid[nxt.fs][0] = nxt.sc;
		dep[nxt.fs] = dep[now]+1;
		dfs(nxt.fs);
	}
	return;
}

void GO(){
	par[1][0] = 1;
	dfs(1);
}

void add_edge(int a,int b,int from){
	if(dep[a]<dep[b])swap(a,b);
	int d = dep[a]-dep[b];
	for(int i = 19;i>=0;i--){
		if(d&(1<<i)){
			ADDEDGE(from,vid[a][i]);
			a = par[a][i];
		}
	}
	for(int i = 19;i>=0;i--){
		if(par[a][i] != par[b][i]){
			ADDEDGE(from,vid[a][i]);
			ADDEDGE(from,vid[b][i]);
			a = par[a][i];
			b = par[b][i];
		}
	}
	if(a != b){
		ADDEDGE(from,vid[a][0]);
		ADDEDGE(from,vid[b][0]);
	}
	return;
}

}

namespace DAG{

int deg[mxn*30];
int ans[mxn];

void TOPO(){
	priority_queue<pii,vector<pii>,less<pii>> pq;
	int C = M;
	for(int i = 0;i<=ppp;i++){
		for(int eid = head[i];eid>0;eid = pre[eid]){
			deg[to[eid]]++;
		}
	}
	for(int i = 0;i<=ppp;i++){
		if(!deg[i]){
			if(i>=1&&i<=M)pq.push(make_pair(i,i));
			else pq.push(make_pair(mxn,i));
		}
	}
	while(!pq.empty()){
		auto now = pq.top().sc;
		pq.pop();
		if(now>=1&&now<=M){
			ans[now] = C--;
		}
		for(int eid = head[now];eid>0;eid = pre[eid]){
			int nxt = to[eid];
			deg[nxt]--;
			if(!deg[nxt]){
				if(nxt>=1&&nxt<=M)pq.push({nxt,nxt});
				else pq.push({mxn,nxt});
			}
		}
	}
	return;
}

void GET(){
	for(int i = 1;i<=M;i++)assert(ans[i]);
	for(int i = 1;i<=M;i++)cout<<ans[i]<<' ';cout<<'\n';
	return;
}

}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M;
	ppp = M+1;
	for(int i = 1;i<=M;i++){
		cin>>edges[i].fs>>edges[i].sc;
	}
	for(int i = 1;i<N;i++){
		int id;
		cin>>id;
		need[id] = true;
		TREE::tree[edges[id].fs].push_back({edges[id].sc,id});
		TREE::tree[edges[id].sc].push_back({edges[id].fs,id});
	}
	TREE::GO();
	for(int i = 1;i<=M;i++){
		if(!need[i])TREE::add_edge(edges[i].fs,edges[i].sc,i);
	}
	DAG::TOPO();
	DAG::GET();
}

Compilation message

riggedroads.cpp: In function 'void DAG::GET()':
riggedroads.cpp:125:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  125 |  for(int i = 1;i<=M;i++)cout<<ans[i]<<' ';cout<<'\n';
      |  ^~~
riggedroads.cpp:125:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  125 |  for(int i = 1;i<=M;i++)cout<<ans[i]<<' ';cout<<'\n';
      |                                           ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16732 KB Output is correct
2 Correct 3 ms 16872 KB Output is correct
3 Correct 3 ms 16728 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16732 KB Output is correct
2 Correct 3 ms 16872 KB Output is correct
3 Correct 3 ms 16728 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 4 ms 17140 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 5 ms 16984 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 86636 KB Output is correct
2 Correct 286 ms 109304 KB Output is correct
3 Correct 128 ms 49480 KB Output is correct
4 Correct 537 ms 210360 KB Output is correct
5 Correct 555 ms 218808 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 103856 KB Output is correct
2 Correct 133 ms 50900 KB Output is correct
3 Correct 61 ms 35756 KB Output is correct
4 Correct 317 ms 79228 KB Output is correct
5 Correct 76 ms 42200 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 190856 KB Output is correct
2 Correct 591 ms 210632 KB Output is correct
3 Correct 158 ms 74404 KB Output is correct
4 Correct 232 ms 97924 KB Output is correct
5 Correct 713 ms 232904 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 134896 KB Output is correct
2 Correct 270 ms 97996 KB Output is correct
3 Correct 777 ms 211300 KB Output is correct
4 Correct 775 ms 195012 KB Output is correct
5 Correct 53 ms 36812 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16732 KB Output is correct
2 Correct 3 ms 16872 KB Output is correct
3 Correct 3 ms 16728 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 4 ms 17140 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 5 ms 16984 KB Output is correct
9 Correct 185 ms 86636 KB Output is correct
10 Correct 286 ms 109304 KB Output is correct
11 Correct 128 ms 49480 KB Output is correct
12 Correct 537 ms 210360 KB Output is correct
13 Correct 555 ms 218808 KB Output is correct
14 Correct 452 ms 103856 KB Output is correct
15 Correct 133 ms 50900 KB Output is correct
16 Correct 61 ms 35756 KB Output is correct
17 Correct 317 ms 79228 KB Output is correct
18 Correct 76 ms 42200 KB Output is correct
19 Correct 547 ms 190856 KB Output is correct
20 Correct 591 ms 210632 KB Output is correct
21 Correct 158 ms 74404 KB Output is correct
22 Correct 232 ms 97924 KB Output is correct
23 Correct 713 ms 232904 KB Output is correct
24 Correct 423 ms 134896 KB Output is correct
25 Correct 270 ms 97996 KB Output is correct
26 Correct 777 ms 211300 KB Output is correct
27 Correct 775 ms 195012 KB Output is correct
28 Correct 53 ms 36812 KB Output is correct
29 Correct 1180 ms 192004 KB Output is correct
30 Correct 1232 ms 206404 KB Output is correct
31 Correct 789 ms 208028 KB Output is correct
32 Correct 168 ms 53140 KB Output is correct
33 Correct 830 ms 209480 KB Output is correct