oj.uz

Submission #909518

# Submission time Handle Problem Language Result Execution time Memory
909518 2024-01-17T08:34:34 Z 12345678 Rigged Roads (NOI19_riggedroads) C++17
68 / 100
 787 ms 94952 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);
    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 14 ms 37980 KB Output is correct
2 Correct 11 ms 37720 KB Output is correct
3 Correct 13 ms 37724 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 37980 KB Output is correct
2 Correct 11 ms 37720 KB Output is correct
3 Correct 13 ms 37724 KB Output is correct
4 Correct 15 ms 37724 KB Output is correct
5 Correct 13 ms 37936 KB Output is correct
6 Correct 14 ms 37984 KB Output is correct
7 Correct 12 ms 37724 KB Output is correct
8 Correct 14 ms 37720 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 50712 KB Output is correct
2 Correct 171 ms 62184 KB Output is correct
3 Correct 311 ms 60288 KB Output is correct
4 Correct 171 ms 76216 KB Output is correct
5 Correct 166 ms 78776 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 66576 KB Output is correct
2 Correct 136 ms 52436 KB Output is correct
3 Correct 67 ms 44048 KB Output is correct
4 Correct 123 ms 58576 KB Output is correct
5 Correct 36 ms 45904 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 84604 KB Output is correct
2 Correct 354 ms 94952 KB Output is correct
3 Correct 59 ms 52436 KB Output is correct
4 Correct 94 ms 61776 KB Output is correct
5 Correct 408 ms 94412 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 71580 KB Output is correct
2 Correct 135 ms 62312 KB Output is correct
3 Correct 521 ms 87636 KB Output is correct
4 Correct 526 ms 84356 KB Output is correct
5 Correct 29 ms 41560 KB Output is correct

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 37980 KB Output is correct
2 Correct 11 ms 37720 KB Output is correct
3 Correct 13 ms 37724 KB Output is correct
4 Correct 15 ms 37724 KB Output is correct
5 Correct 13 ms 37936 KB Output is correct
6 Correct 14 ms 37984 KB Output is correct
7 Correct 12 ms 37724 KB Output is correct
8 Correct 14 ms 37720 KB Output is correct
9 Correct 66 ms 50712 KB Output is correct
10 Correct 171 ms 62184 KB Output is correct
11 Correct 311 ms 60288 KB Output is correct
12 Correct 171 ms 76216 KB Output is correct
13 Correct 166 ms 78776 KB Output is correct
14 Correct 165 ms 66576 KB Output is correct
15 Correct 136 ms 52436 KB Output is correct
16 Correct 67 ms 44048 KB Output is correct
17 Correct 123 ms 58576 KB Output is correct
18 Correct 36 ms 45904 KB Output is correct
19 Correct 317 ms 84604 KB Output is correct
20 Correct 354 ms 94952 KB Output is correct
21 Correct 59 ms 52436 KB Output is correct
22 Correct 94 ms 61776 KB Output is correct
23 Correct 408 ms 94412 KB Output is correct
24 Correct 267 ms 71580 KB Output is correct
25 Correct 135 ms 62312 KB Output is correct
26 Correct 521 ms 87636 KB Output is correct
27 Correct 526 ms 84356 KB Output is correct
28 Correct 29 ms 41560 KB Output is correct
29 Incorrect 787 ms 90260 KB Output isn't correct
30 Halted 0 ms 0 KB -