oj.uz

Submission #909565

# Submission time Handle Problem Language Result Execution time Memory
909565 2024-01-17T09:16:33 Z 12345678 Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 788 ms 90052 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=3e5+5, kx=19;

int n, m, x, t[nx], cnt, ans[nx], used[nx], sz[nx], pa[nx][kx], lvl[nx];
vector<int> vl[nx], add[nx], rem[nx];
vector<pair<int, int>> ed(nx), d[nx];
set<int> s;

void dfs(int u, int p)
{
    lvl[u]=lvl[p]+1;
    pa[u][0]=p;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    for (auto [v, w]:d[u]) if (v!=p) dfs(v, u);
}

void dfssz(int u, int p)
{
    sz[u]=(int)add[u].size()+(int)rem[u].size()+1;
    for (auto [v, w]:d[u]) if (v!=p) dfssz(v, u), sz[u]+=sz[v];    
}

int lca(int u, int v)
{
    if (lvl[u]>lvl[v]) swap(u, v);
    for (int i=kx-1; i>=0; i--) if (lvl[pa[v][i]]>=lvl[u]) v=pa[v][i];
    if (u==v) return u;
    for (int i=kx-1; i>=0; i--) if (pa[u][i]!=pa[v][i]) u=pa[u][i], v=pa[v][i];
    return pa[u][0];
}

void dfsadd(int u, int p)
{
    for (auto [v, w]:d[u]) if (v!=p) dfsadd(v, u);
    for (auto tmp:add[u]) s.insert(tmp);
    for (auto tmp:rem[u]) s.erase(tmp);
}

void sack(int u, int p, int idx, int del)
{
    pair<int, int> hv={-1, -1};
    for (auto [v, w]:d[u]) if (v!=p) hv=max(hv, {sz[v], v});
    for (auto [v, w]:d[u]) if (v!=p&&v!=hv.second) sack(v, u, w, 1);
    for (auto [v, w]:d[u]) if (v!=p&&v==hv.second) sack(v, u, w, 0);
    for (auto [v, w]:d[u]) if (v!=p&&v!=hv.second) dfsadd(v, u);
    for (auto tmp:add[u]) s.insert(tmp);
    for (auto tmp:rem[u]) s.erase(tmp);
    if (s.size()>0&&*s.begin()<idx) used[idx]=1, vl[*s.begin()].push_back(idx);
    if (del) s.clear();
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=m; i++) cin>>ed[i].first>>ed[i].second;
    for (int i=1; i<n; i++) cin>>x, t[x]=1, d[ed[x].first].push_back({ed[x].second, x}), d[ed[x].second].push_back({ed[x].first, x});
    dfs(1, 1);
    for (int i=1; i<=m; i++) if (!t[i]) add[ed[i].first].push_back(i), add[ed[i].second].push_back(i), rem[lca(ed[i].first, ed[i].second)].push_back(i);
    dfssz(1, 1);
    sack(1, 1, 0, 0);
    //for (int i=1; i<=n; i++) cout<<i<<' '<<sz[i]<<'\n';
    for (int i=1; i<=m; i++)
    {
        if (t[i]&&!used[i]) ans[i]=++cnt;
        else if (!t[i])
        {
            sort(vl[i].begin(), vl[i].end());
            for (auto tmp:vl[i]) ans[tmp]=++cnt;
            ans[i]=++cnt;
        }
    }
    for (int i=1; i<=m; i++) cout<<ans[i]<<' ';
}

/*
4 6
2 3
3 4
2 4
1 3
1 4
1 2
1 2 6
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 37724 KB Output is correct
2 Correct 11 ms 37828 KB Output is correct
3 Correct 12 ms 37724 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 37724 KB Output is correct
2 Correct 11 ms 37828 KB Output is correct
3 Correct 12 ms 37724 KB Output is correct
4 Correct 13 ms 37724 KB Output is correct
5 Correct 12 ms 37724 KB Output is correct
6 Correct 12 ms 37812 KB Output is correct
7 Correct 12 ms 37724 KB Output is correct
8 Correct 13 ms 37724 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 49320 KB Output is correct
2 Correct 187 ms 59548 KB Output is correct
3 Correct 291 ms 57284 KB Output is correct
4 Correct 133 ms 73404 KB Output is correct
5 Correct 151 ms 75328 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 64284 KB Output is correct
2 Correct 141 ms 50856 KB Output is correct
3 Correct 65 ms 43332 KB Output is correct
4 Correct 115 ms 56868 KB Output is correct
5 Correct 40 ms 45336 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 80028 KB Output is correct
2 Correct 446 ms 90052 KB Output is correct
3 Correct 58 ms 51148 KB Output is correct
4 Correct 83 ms 59732 KB Output is correct
5 Correct 463 ms 88640 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 68552 KB Output is correct
2 Correct 128 ms 60368 KB Output is correct
3 Correct 629 ms 82332 KB Output is correct
4 Correct 505 ms 79788 KB Output is correct
5 Correct 33 ms 41096 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 37724 KB Output is correct
2 Correct 11 ms 37828 KB Output is correct
3 Correct 12 ms 37724 KB Output is correct
4 Correct 13 ms 37724 KB Output is correct
5 Correct 12 ms 37724 KB Output is correct
6 Correct 12 ms 37812 KB Output is correct
7 Correct 12 ms 37724 KB Output is correct
8 Correct 13 ms 37724 KB Output is correct
9 Correct 66 ms 49320 KB Output is correct
10 Correct 187 ms 59548 KB Output is correct
11 Correct 291 ms 57284 KB Output is correct
12 Correct 133 ms 73404 KB Output is correct
13 Correct 151 ms 75328 KB Output is correct
14 Correct 230 ms 64284 KB Output is correct
15 Correct 141 ms 50856 KB Output is correct
16 Correct 65 ms 43332 KB Output is correct
17 Correct 115 ms 56868 KB Output is correct
18 Correct 40 ms 45336 KB Output is correct
19 Correct 329 ms 80028 KB Output is correct
20 Correct 446 ms 90052 KB Output is correct
21 Correct 58 ms 51148 KB Output is correct
22 Correct 83 ms 59732 KB Output is correct
23 Correct 463 ms 88640 KB Output is correct
24 Correct 253 ms 68552 KB Output is correct
25 Correct 128 ms 60368 KB Output is correct
26 Correct 629 ms 82332 KB Output is correct
27 Correct 505 ms 79788 KB Output is correct
28 Correct 33 ms 41096 KB Output is correct
29 Correct 788 ms 85204 KB Output is correct
30 Correct 711 ms 81100 KB Output is correct
31 Correct 640 ms 73936 KB Output is correct
32 Correct 301 ms 52052 KB Output is correct
33 Correct 536 ms 74080 KB Output is correct