oj.uz

Submission #909424

# Submission time Handle Problem Language Result Execution time Memory
909424 2024-01-17T08:05:26 Z 12345678 Rigged Roads (NOI19_riggedroads) C++17
56 / 100
 2000 ms 94920 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();
    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);
    //cout<<"here "<<u<<' '<<s.size()<<':';
    //for (auto x:s) cout<<x<<' ';
    //cout<<'\n';
    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<=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]<<' ';
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 37976 KB Output is correct
2 Correct 12 ms 37712 KB Output is correct
3 Correct 12 ms 37724 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 37976 KB Output is correct
2 Correct 12 ms 37712 KB Output is correct
3 Correct 12 ms 37724 KB Output is correct
4 Correct 13 ms 37724 KB Output is correct
5 Correct 12 ms 37876 KB Output is correct
6 Correct 14 ms 37980 KB Output is correct
7 Correct 14 ms 37724 KB Output is correct
8 Correct 13 ms 37720 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 50632 KB Output is correct
2 Correct 197 ms 62172 KB Output is correct
3 Correct 294 ms 60376 KB Output is correct
4 Correct 140 ms 75912 KB Output is correct
5 Correct 163 ms 77484 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 66744 KB Output is correct
2 Correct 137 ms 52372 KB Output is correct
3 Correct 68 ms 44100 KB Output is correct
4 Correct 120 ms 58576 KB Output is correct
5 Correct 38 ms 45840 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 84348 KB Output is correct
2 Correct 388 ms 94920 KB Output is correct
3 Correct 56 ms 52432 KB Output is correct
4 Correct 100 ms 61776 KB Output is correct
5 Correct 522 ms 93924 KB Output is correct

Subtask #6
0 / 12.0

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

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 37976 KB Output is correct
2 Correct 12 ms 37712 KB Output is correct
3 Correct 12 ms 37724 KB Output is correct
4 Correct 13 ms 37724 KB Output is correct
5 Correct 12 ms 37876 KB Output is correct
6 Correct 14 ms 37980 KB Output is correct
7 Correct 14 ms 37724 KB Output is correct
8 Correct 13 ms 37720 KB Output is correct
9 Correct 67 ms 50632 KB Output is correct
10 Correct 197 ms 62172 KB Output is correct
11 Correct 294 ms 60376 KB Output is correct
12 Correct 140 ms 75912 KB Output is correct
13 Correct 163 ms 77484 KB Output is correct
14 Correct 158 ms 66744 KB Output is correct
15 Correct 137 ms 52372 KB Output is correct
16 Correct 68 ms 44100 KB Output is correct
17 Correct 120 ms 58576 KB Output is correct
18 Correct 38 ms 45840 KB Output is correct
19 Correct 326 ms 84348 KB Output is correct
20 Correct 388 ms 94920 KB Output is correct
21 Correct 56 ms 52432 KB Output is correct
22 Correct 100 ms 61776 KB Output is correct
23 Correct 522 ms 93924 KB Output is correct
24 Execution timed out 2021 ms 69964 KB Time limit exceeded
25 Halted 0 ms 0 KB -