Submission #248681

#	Time	Username	Problem	Language	Result	Execution time	Memory
248681		SamAnd	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	688 ms	82872 KiB

riggedroads

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 300005;

int n, m;
pair<int, int> b[N];
int u[N];

vector<int> t[N], ti[N];

const int k = 19;
int p[N][k];
int k0[N];
int tin[N], tout[N], tim;

void dfs0(int x, int p0)
{
    tin[x] = ++tim;
    p[x][0] = p0;
    for (int i = 1; i < k; ++i)
    {
        p[x][i] = p[p[x][i - 1]][i - 1];
    }
    for (int i = 0; i < t[x].size(); ++i)
    {
        int h = t[x][i];
        int hi = ti[x][i];
        if (h == p0)
            continue;
        k0[h] = hi;
        dfs0(h, x);
    }
    tout[x] = tim;
}

bool isp(int x, int y)
{
    return (tin[x] <= tin[y] && tout[y] <= tout[x]);
}

int lca(int x, int y)
{
    if (isp(x, y))
        return x;
    if (isp(y, x))
        return y;
    for (int i = k - 1; i >= 0; --i)
    {
        if (!isp(p[x][i], y))
            x = p[x][i];
    }
    return p[x][0];
}

int p0[N];
int fi(int x)
{
    if (x == p0[x])
        return x;
    return p0[x] = fi(p0[x]);
}

int z;
int ans[N];

void solv()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d%d", &b[i].fi, &b[i].se);
    }
    for (int i = 1; i <= n - 1; ++i)
    {
        scanf("%d", &u[i]);
        t[b[u[i]].fi].push_back(b[u[i]].se);
        t[b[u[i]].se].push_back(b[u[i]].fi);
        ti[b[u[i]].fi].push_back(u[i]);
        ti[b[u[i]].se].push_back(u[i]);
    }
    sort(u + 1, u + n);
    dfs0(1, 1);
    for (int x = 1; x <= n; ++x)
        p0[x] = x;

    for (int i = 1; i <= m; ++i)
    {
        int x = b[i].fi;
        int y = b[i].se;

        if (binary_search(u + 1, u + n, i))
        {
            if (isp(x, y))
                swap(x, y);
            if (fi(x) != x)
                continue;
            p0[x] = y;
            ans[k0[x]] = ++z;
            continue;
        }

        int l = lca(x, y);

        vector<int> v;
        while (1)
        {
            x = fi(x);
            if (isp(x, l))
                break;
            p0[x] = p[x][0];
            v.push_back(k0[x]);
        }

        swap(x, y);
        while (1)
        {
            x = fi(x);
            if (isp(x, l))
                break;
            p0[x] = p[x][0];
            v.push_back(k0[x]);
        }

        sort(all(v));
        for (int i = 0; i < v.size(); ++i)
            ans[v[i]] = ++z;

        ans[i] = ++z;
    }
    for (int i = 1; i <= m; ++i)
        printf("%d ", ans[i]);
    printf("\n");
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    solv();
    return 0;
}

//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}

Compilation message (stderr)

riggedroads.cpp: In function 'void dfs0(int, int)':
riggedroads.cpp:32:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < t[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
riggedroads.cpp: In function 'void solv()':
riggedroads.cpp:133:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < v.size(); ++i)
                         ~~^~~~~~~~~~
riggedroads.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
riggedroads.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &b[i].fi, &b[i].se);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &u[i]);
         ~~~~~^~~~~~~~~~~~~

• 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