oj.uz

Submission #909500

# Submission time Handle Problem Language Result Execution time Memory
909500 2024-01-17T08:30:23 Z 12345678 Rigged Roads (NOI19_riggedroads) C++17
68 / 100
 757 ms 102600 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

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

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 12 ms 37720 KB Output is correct
2 Correct 10 ms 37724 KB Output is correct
3 Correct 13 ms 37836 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 37720 KB Output is correct
2 Correct 10 ms 37724 KB Output is correct
3 Correct 13 ms 37836 KB Output is correct
4 Correct 11 ms 37720 KB Output is correct
5 Correct 12 ms 37720 KB Output is correct
6 Correct 12 ms 37980 KB Output is correct
7 Correct 12 ms 37720 KB Output is correct
8 Correct 11 ms 37832 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 49564 KB Output is correct
2 Correct 172 ms 62848 KB Output is correct
3 Correct 292 ms 60656 KB Output is correct
4 Correct 124 ms 74772 KB Output is correct
5 Correct 156 ms 74944 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 71708 KB Output is correct
2 Correct 152 ms 52916 KB Output is correct
3 Correct 70 ms 44488 KB Output is correct
4 Correct 120 ms 63032 KB Output is correct
5 Correct 38 ms 46932 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 89812 KB Output is correct
2 Correct 381 ms 102600 KB Output is correct
3 Correct 70 ms 56268 KB Output is correct
4 Correct 89 ms 64080 KB Output is correct
5 Correct 365 ms 97484 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 77232 KB Output is correct
2 Correct 159 ms 65364 KB Output is correct
3 Correct 498 ms 91872 KB Output is correct
4 Correct 478 ms 85748 KB Output is correct
5 Correct 28 ms 41308 KB Output is correct

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 37720 KB Output is correct
2 Correct 10 ms 37724 KB Output is correct
3 Correct 13 ms 37836 KB Output is correct
4 Correct 11 ms 37720 KB Output is correct
5 Correct 12 ms 37720 KB Output is correct
6 Correct 12 ms 37980 KB Output is correct
7 Correct 12 ms 37720 KB Output is correct
8 Correct 11 ms 37832 KB Output is correct
9 Correct 58 ms 49564 KB Output is correct
10 Correct 172 ms 62848 KB Output is correct
11 Correct 292 ms 60656 KB Output is correct
12 Correct 124 ms 74772 KB Output is correct
13 Correct 156 ms 74944 KB Output is correct
14 Correct 195 ms 71708 KB Output is correct
15 Correct 152 ms 52916 KB Output is correct
16 Correct 70 ms 44488 KB Output is correct
17 Correct 120 ms 63032 KB Output is correct
18 Correct 38 ms 46932 KB Output is correct
19 Correct 352 ms 89812 KB Output is correct
20 Correct 381 ms 102600 KB Output is correct
21 Correct 70 ms 56268 KB Output is correct
22 Correct 89 ms 64080 KB Output is correct
23 Correct 365 ms 97484 KB Output is correct
24 Correct 253 ms 77232 KB Output is correct
25 Correct 159 ms 65364 KB Output is correct
26 Correct 498 ms 91872 KB Output is correct
27 Correct 478 ms 85748 KB Output is correct
28 Correct 28 ms 41308 KB Output is correct
29 Incorrect 757 ms 91800 KB Output isn't correct
30 Halted 0 ms 0 KB -