Submission #1252526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252526		nasjes	Rigged Roads (NOI19_riggedroads)	C++20	100 / 100	414 ms	155828 KiB

riggedroads

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 1e6+7;
//const ll mod = 1e9 + 7;
const ll inf = 1e17 + 77;
//#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>

ll n, m,k, t;
ll boss[dim];
pll a[dim];
vector<pll> g[dim];
ll vis[dim];
ll mn[dim], tin[dim], tout[dim];
ll jump[dim][30];
ll depth[dim];
ll par[dim];
ll tt=0;
ll up[dim];
ll findboss(ll v){
    if(boss[v]==v)return v;
    return boss[v]=findboss(boss[v]);
}
bool team(ll x, ll y){
    return (findboss(x)==findboss(y));
}
void unite(ll x, ll y){
    ll xx=findboss(x);
    ll yy=findboss(y);
    if(depth[xx]>depth[yy])swap(xx, yy);
    boss[yy]=xx;
}
ll same(ll x, ll y){
    if(tin[x]<=tin[y] && tout[y]<=tout[x])return 1;
    swap(x, y);
    if(tin[x]<=tin[y] && tout[y]<=tout[x])return 1;
    return 0;
}

void dfs(ll v, ll p, ll d, ll w){
    tt++;
    tin[v]=tt;
    par[v]=p;
    jump[v][0]=p;
    depth[v]=d;
    up[v]=w;
    for(int i=1; i<=20; i++){
        jump[v][i]=jump[jump[v][i-1]][i-1];
    }
    for(auto el: g[v]){
        if(el.fi==p)continue;
        dfs(el.fi, v, d+1, el.se);
    }
    tt++;
    tout[v]=tt;
}

ll lca(ll x, ll y){
    if(depth[x]<depth[y])swap(x, y);
    if(same(x, y)){return y;}
    ll cur=x;
    for(int i=20; i>=0; i--){
        if(!same(jump[cur][i], y)){
            cur=jump[cur][i];
        }
    }
    cur=jump[cur][0];
    return cur;
}
set<ll> top;
void go(ll v, ll aim){
  //  cout<<v<<" "<<aim<<endl;
    if(team(v, aim))return;
    ll nw=findboss(v);
    unite(nw, par[nw]);
    top.insert(up[nw]);
    go(par[nw], aim);
}
int main() {

    ll  u,v, w, q, l, r;
    cin>>n>>m;
    set<ll> s;
    for(int i=1; i<=m; i++){
        cin>>u>>v;
        a[i]={u, v};
    }
    for(int i=1; i<=n; i++)boss[i]=i;
    vll d;
    for(int i=1; i<=n-1; i++){
        cin>>u;
        d.pb(u);
        g[a[u].fi].pb({a[u].se, u});
        g[a[u].se].pb({a[u].fi, u});
        vis[u]=1;
    }
    ll root=a[u].fi;
   // cout<<root<<endl;
    dfs(root, root, 1, 0);
    ll cnt=1;
    for(int i=1; i<=m; i++){
        if(team(a[i].fi, a[i].se)){
            if(mn[i]==0){mn[i]=cnt;cnt++;}
           continue;
        }
        ll lc=lca(a[i].fi, a[i].se);
       // cout<<a[i].fi<<" "<<a[i].se<<" "<<lc<<endl;
        top.clear();
        ll add=0;
        go(a[i].fi, lc);
        go(a[i].se, lc);
        top.erase(i);
        for(auto x: top){
            mn[x]=cnt+add;
            add++;
        }
        mn[i]=cnt+add;
        cnt=mn[i]+1;
    }

    for(int i=1; i<=m; i++){
        cout<<mn[i]<<" ";
    }
    cout<<endl;

    return 0;
}

• 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