oj.uz

Submission #909563

# Submission time Handle Problem Language Result Execution time Memory
909563 2024-01-17T09:15:01 Z 12345678 Rigged Roads (NOI19_riggedroads) C++17
68 / 100
 793 ms 131244 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=6e5+5, kx=22;

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);
    if (!del) 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 23 ms 72988 KB Output is correct
2 Correct 25 ms 72796 KB Output is correct
3 Correct 24 ms 72796 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 72988 KB Output is correct
2 Correct 25 ms 72796 KB Output is correct
3 Correct 24 ms 72796 KB Output is correct
4 Correct 24 ms 72980 KB Output is correct
5 Correct 24 ms 73052 KB Output is correct
6 Correct 24 ms 73052 KB Output is correct
7 Correct 22 ms 73048 KB Output is correct
8 Correct 23 ms 73052 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 88564 KB Output is correct
2 Correct 212 ms 98480 KB Output is correct
3 Correct 444 ms 95968 KB Output is correct
4 Correct 171 ms 111304 KB Output is correct
5 Correct 196 ms 114872 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 103320 KB Output is correct
2 Correct 166 ms 87748 KB Output is correct
3 Correct 97 ms 82724 KB Output is correct
4 Correct 166 ms 96076 KB Output is correct
5 Correct 63 ms 82524 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 120900 KB Output is correct
2 Correct 324 ms 130668 KB Output is correct
3 Correct 90 ms 90400 KB Output is correct
4 Correct 105 ms 96852 KB Output is correct
5 Correct 484 ms 131244 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 107720 KB Output is correct
2 Correct 182 ms 97592 KB Output is correct
3 Correct 637 ms 123140 KB Output is correct
4 Correct 521 ms 118288 KB Output is correct
5 Correct 40 ms 78412 KB Output is correct

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 72988 KB Output is correct
2 Correct 25 ms 72796 KB Output is correct
3 Correct 24 ms 72796 KB Output is correct
4 Correct 24 ms 72980 KB Output is correct
5 Correct 24 ms 73052 KB Output is correct
6 Correct 24 ms 73052 KB Output is correct
7 Correct 22 ms 73048 KB Output is correct
8 Correct 23 ms 73052 KB Output is correct
9 Correct 80 ms 88564 KB Output is correct
10 Correct 212 ms 98480 KB Output is correct
11 Correct 444 ms 95968 KB Output is correct
12 Correct 171 ms 111304 KB Output is correct
13 Correct 196 ms 114872 KB Output is correct
14 Correct 186 ms 103320 KB Output is correct
15 Correct 166 ms 87748 KB Output is correct
16 Correct 97 ms 82724 KB Output is correct
17 Correct 166 ms 96076 KB Output is correct
18 Correct 63 ms 82524 KB Output is correct
19 Correct 415 ms 120900 KB Output is correct
20 Correct 324 ms 130668 KB Output is correct
21 Correct 90 ms 90400 KB Output is correct
22 Correct 105 ms 96852 KB Output is correct
23 Correct 484 ms 131244 KB Output is correct
24 Correct 279 ms 107720 KB Output is correct
25 Correct 182 ms 97592 KB Output is correct
26 Correct 637 ms 123140 KB Output is correct
27 Correct 521 ms 118288 KB Output is correct
28 Correct 40 ms 78412 KB Output is correct
29 Incorrect 793 ms 123708 KB Output isn't correct
30 Halted 0 ms 0 KB -