oj.uz

Submission #909510

# Submission time Handle Problem Language Result Execution time Memory
909510 2024-01-17T08:33:07 Z 12345678 Rigged Roads (NOI19_riggedroads) C++17
68 / 100
 726 ms 99564 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+100, 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);
    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 37724 KB Output is correct
2 Correct 11 ms 37724 KB Output is correct
3 Correct 13 ms 37980 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 37724 KB Output is correct
3 Correct 13 ms 37980 KB Output is correct
4 Correct 11 ms 37720 KB Output is correct
5 Correct 11 ms 37724 KB Output is correct
6 Correct 13 ms 37976 KB Output is correct
7 Correct 13 ms 37928 KB Output is correct
8 Correct 11 ms 37724 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 49408 KB Output is correct
2 Correct 167 ms 59820 KB Output is correct
3 Correct 318 ms 57532 KB Output is correct
4 Correct 128 ms 72120 KB Output is correct
5 Correct 145 ms 73640 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 69224 KB Output is correct
2 Correct 143 ms 52304 KB Output is correct
3 Correct 72 ms 44116 KB Output is correct
4 Correct 115 ms 60368 KB Output is correct
5 Correct 38 ms 46936 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 86692 KB Output is correct
2 Correct 375 ms 99564 KB Output is correct
3 Correct 57 ms 53964 KB Output is correct
4 Correct 95 ms 63824 KB Output is correct
5 Correct 442 ms 96176 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 74636 KB Output is correct
2 Correct 151 ms 65100 KB Output is correct
3 Correct 467 ms 88804 KB Output is correct
4 Correct 477 ms 84972 KB Output is correct
5 Correct 25 ms 41052 KB Output is correct

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 37724 KB Output is correct
2 Correct 11 ms 37724 KB Output is correct
3 Correct 13 ms 37980 KB Output is correct
4 Correct 11 ms 37720 KB Output is correct
5 Correct 11 ms 37724 KB Output is correct
6 Correct 13 ms 37976 KB Output is correct
7 Correct 13 ms 37928 KB Output is correct
8 Correct 11 ms 37724 KB Output is correct
9 Correct 57 ms 49408 KB Output is correct
10 Correct 167 ms 59820 KB Output is correct
11 Correct 318 ms 57532 KB Output is correct
12 Correct 128 ms 72120 KB Output is correct
13 Correct 145 ms 73640 KB Output is correct
14 Correct 170 ms 69224 KB Output is correct
15 Correct 143 ms 52304 KB Output is correct
16 Correct 72 ms 44116 KB Output is correct
17 Correct 115 ms 60368 KB Output is correct
18 Correct 38 ms 46936 KB Output is correct
19 Correct 292 ms 86692 KB Output is correct
20 Correct 375 ms 99564 KB Output is correct
21 Correct 57 ms 53964 KB Output is correct
22 Correct 95 ms 63824 KB Output is correct
23 Correct 442 ms 96176 KB Output is correct
24 Correct 291 ms 74636 KB Output is correct
25 Correct 151 ms 65100 KB Output is correct
26 Correct 467 ms 88804 KB Output is correct
27 Correct 477 ms 84972 KB Output is correct
28 Correct 25 ms 41052 KB Output is correct
29 Incorrect 726 ms 90760 KB Output isn't correct
30 Halted 0 ms 0 KB -