Submission #209755

#	Time	Username	Problem	Language	Result	Execution time	Memory
209755		Alexa2001	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	613 ms	55288 KiB

riggedroads

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const int Nmax = 3e5 + 5, lg = 18;

vector<int> v[Nmax];
int x[Nmax], y[Nmax], n, m, tmp, ans[Nmax], val[Nmax], w[Nmax];
int t[lg+2][Nmax];

bool used[Nmax];
int level[Nmax];


struct forest
{
    int t[Nmax];

    void unite(int x, int y)
    {
        t[x] = y;
    }

    int boss(int x)
    {
        if(x == t[x]) return x;
        return t[x] = boss(t[x]);
    }

    void init()
    {
        iota(t+1, t+n+1, 1);
    }
} f;



void dfs(int node, int dad = 0)
{
    t[0][node] = dad;
    level[node] = level[dad] + 1;

    int i;
    for(i=1; i<=lg; ++i)
        t[i][node] = t[i-1][t[i-1][node]];

    for(auto it : v[node])
        if(it != dad)
            dfs(it, node);
}

int lca(int x, int y)
{
    if(level[x] < level[y]) swap(x, y);
    int up = level[x] - level[y], i;

    for(i=0; i<=lg; ++i)
        if(up & (1<<i)) x = t[i][x];

    if(x == y) return x;

    for(i=lg; i>=0; --i)
        if(t[i][x] != t[i][y])
            x = t[i][x], y = t[i][y];
    return t[0][x];
}

int solve(int x, int y, int id)
{
    int l = lca(x, y);
    int nr = 0;

    x = f.boss(x);
    while(level[x] > level[l])
    {
        f.unite(x, t[0][x]);
        ++nr;
        w[x] = id;
        x = f.boss(x);
    }

    y = f.boss(y);
    while(level[y] > level[l])
    {
        f.unite(y, t[0][y]);
        ++nr;
        w[y] = id;
        y = f.boss(y);
    }
    return nr;
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    cin >> n >> m;
    int i;
    for(i=1; i<=m; ++i)
        cin >> x[i] >> y[i];

    for(i=1; i<n; ++i)
    {
        int id;
        cin >> id;
        used[id] = 1;

        v[x[id]].pb(y[id]);
        v[y[id]].pb(x[id]);
    }

    dfs(1);
    f.init();

    int nr = 0;

    for(i=1; i<=m; ++i)
        if(used[i])
        {
            if(level[x[i]] < level[y[i]]) swap(x[i], y[i]);

            if(w[x[i]])
                ans[i] = ++val[w[x[i]]];
            else
            {
                ans[i] = ++nr;
                f.unite(x[i], y[i]);
            }
        }
        else
        {
            val[i] = nr;
            nr += solve(x[i], y[i], i);
            ans[i] = ++nr;
        }

    for(i=1; i<=m; ++i) cout << ans[i] << ' ';

    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