oj.uz

Submission #909438

# Submission time Handle Problem Language Result Execution time Memory
909438 2024-01-17T08:11:13 Z 12345678 Rigged Roads (NOI19_riggedroads) C++17
56 / 100
 2000 ms 99692 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=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();
    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 11 ms 37812 KB Output is correct
2 Correct 11 ms 37720 KB Output is correct
3 Correct 10 ms 37724 KB Output is correct

Subtask #2
19.0 / 19.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 49352 KB Output is correct
2 Correct 185 ms 59572 KB Output is correct
3 Correct 425 ms 57392 KB Output is correct
4 Correct 161 ms 72856 KB Output is correct
5 Correct 169 ms 75424 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 69192 KB Output is correct
2 Correct 153 ms 52308 KB Output is correct
3 Correct 85 ms 44136 KB Output is correct
4 Correct 114 ms 60352 KB Output is correct
5 Correct 40 ms 46932 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 87096 KB Output is correct
2 Correct 385 ms 99692 KB Output is correct
3 Correct 88 ms 53848 KB Output is correct
4 Correct 93 ms 63648 KB Output is correct
5 Correct 528 ms 96764 KB Output is correct

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2072 ms 73152 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 37812 KB Output is correct
2 Correct 11 ms 37720 KB Output is correct
3 Correct 10 ms 37724 KB Output is correct
4 Correct 12 ms 37724 KB Output is correct
5 Correct 11 ms 37820 KB Output is correct
6 Correct 11 ms 37976 KB Output is correct
7 Correct 12 ms 37724 KB Output is correct
8 Correct 12 ms 37724 KB Output is correct
9 Correct 65 ms 49352 KB Output is correct
10 Correct 185 ms 59572 KB Output is correct
11 Correct 425 ms 57392 KB Output is correct
12 Correct 161 ms 72856 KB Output is correct
13 Correct 169 ms 75424 KB Output is correct
14 Correct 230 ms 69192 KB Output is correct
15 Correct 153 ms 52308 KB Output is correct
16 Correct 85 ms 44136 KB Output is correct
17 Correct 114 ms 60352 KB Output is correct
18 Correct 40 ms 46932 KB Output is correct
19 Correct 414 ms 87096 KB Output is correct
20 Correct 385 ms 99692 KB Output is correct
21 Correct 88 ms 53848 KB Output is correct
22 Correct 93 ms 63648 KB Output is correct
23 Correct 528 ms 96764 KB Output is correct
24 Execution timed out 2072 ms 73152 KB Time limit exceeded
25 Halted 0 ms 0 KB -