| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 901534 | pcc | Rigged Roads (NOI19_riggedroads) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
vector<int> paths[mxn*30];
int ppp;
bitset<mxn> need;
int newnode(){
return ++ppp;
}
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();
paths[vid[now][i]].push_back(vid[now][i-1]);
paths[vid[now][i]].push_back(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)){
paths[from].push_back(vid[a][i]);
a = par[a][i];
}
}
for(int i = 19;i>=0;i--){
if(par[a][i] != par[b][i]){
paths[from].push_back(vid[a][i]);
paths[from].push_back(vid[b][i]);
a = par[a][i];
b = par[b][i];
}
}
if(a != b){
paths[from].push_back(vid[a][0]);
paths[from].push_back(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(auto nxt:paths[i]){
//cout<<i<<','<<nxt<<endl;
deg[nxt]++;
}
}
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(auto nxt:paths[now]){
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(auto &i:paths)i.push_back({1,1});
return 0;
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();
}