Submission #545661

#	Time	Username	Problem	Language	Result	Execution time	Memory
545661		balbit	Rigged Roads (NOI19_riggedroads)	C++14	100 / 100	359 ms	73640 KiB

riggedroads

#include <bits/stdc++.h>
#define int ll
using namespace std;

#define ll long long
#define f first
#define s second
#define pii pair<int, int>

#define MX(a,b) a=max(a,b)
#define MN(a,b) a=min(a,b)
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()

#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do( T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT

const int maxn = 3e5+5;

vector<pii> tree[maxn];
struct edge{
    int u,v,id;
};
vector<edge> G;
bool treeedge[maxn];
int par[maxn], parid[maxn], dep[maxn], L[maxn], R[maxn];
int dsupar[maxn], head[maxn];
int IT =0;
bool headdone[maxn];

void dfs(int v, int p) {
    L[v] = R[v] = IT++;
    for (pii e : tree[v]) {
        int u = e.f;
        if (u!= p) {
            par[u] = v; parid[u] = e.s;
            dep[u] = dep[v] + 1;
            dfs(u,v);
            R[v] = R[u];
        }
    }
}

int find(int x) {
    return x == dsupar[x] ? x : dsupar[x] = find(dsupar[x]);
}

inline bool isanc(int a, int b) {return L[a] <= L[b] && R[a] >= R[b];}

void mrg(int a, int b) {
    a = find(a); b = find(b);
    if (a==b) return;
    if (dep[head[a]] < dep[head[b]]) {
        dsupar[b] = a;
    }else{
        dsupar[a] = b;
    }
}

int AT = 1;
int ans[maxn];

void work(int a, int b, int myid) {
    bug(a,b,myid);
    bug(a, find(a), head[find(a)]);
    if (treeedge[myid]) {
        if (ans[myid] > 0) return;
        ans[myid] = AT++;
        return;
    }
    vector<int> ids;
    REP(tt, 2) {
        int x = a;
        while (1) {
            x = head[find(x)];
            bug(x, b);
            if (!isanc(x,b)) {
                headdone[x] = 1;
                ids.pb(parid[x]);
                mrg(x, par[x]);
            }else break;
        }
        swap(a,b);
    }
    bug(SZ(ids));
    sort(ALL(ids));
    for (int x : ids) bug(x);
    for (int x : ids) {
        if (ans[x]) continue;
        ans[x] = AT++;
    }
    ans[myid] = AT++;
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    bug(1,2);

    int n,m; cin>>n>>m;
    REP(i,m) {
        int a,b; cin>>a>>b; --a; --b;
        G.pb({a,b,i});
    }
    REP(i, n-1) {
        int s; cin>>s;
        --s;
        treeedge[s] = 1;
        tree[G[s].u].pb({G[s].v, s});
        tree[G[s].v].pb({G[s].u, s});
    }
    bug("hey");
    REP(i,n) {
        dsupar[i] = i;
        head[i] = i;
    }
    headdone[0] = 1;
    dfs(0, -1);
    REP(i,n) {
        bug(i, L[i], R[i]);
    }
    bug("yo");
    REP(i, SZ(G)) {
        work(G[i].u, G[i].v, i);
    }
    REP(i,m) {
        cout<<ans[i]<<' ';
    }
        cout<<endl;
}

Compilation message (stderr)

riggedroads.cpp: In function 'void work(long long int, long long int, long long int)':
riggedroads.cpp:97:14: warning: unused variable 'x' [-Wunused-variable]
   97 |     for (int x : ids) bug(x);
      |              ^

• 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