oj.uz

Submission #456227

# Submission time Handle Problem Language Result Execution time Memory
456227 2021-08-06T09:16:54 Z astoria Rigged Roads (NOI19_riggedroads) C++14
100 / 100
 505 ms 67248 KB 
#include <bits/stdc++.h>
using namespace std;

#define maxn 300005
int n,e;
int a[maxn],b[maxn];
int r[maxn];
vector<pair<int,int> > adj[maxn];
int depth[maxn];
int p[maxn][20];
int par[maxn];
bool is[maxn];
int ans[maxn];
int pe[maxn];
int ct;
vector<int> bef;
int lc;

int root (int x){
    if (par[x] == -1) return x;
    else return par[x] = root(par[x]);
}

void connect (int u){
    par[u] = root(p[u][0]);
}

void dfs(int x, int pa){
    p[x][0] = pa;
    for (auto i : adj[x]){
        if (i.first == pa) continue;
        depth[i.first] = depth[x] + 1;
        pe[i.first] = i.second;
        dfs(i.first,x);
    }
}

int lca (int a, int b){
    if (depth[a] < depth[b]) swap(a,b);
    for (int k=19; k>=0; k--){
        if (p[a][k] != -1 && depth[p[a][k]] >= depth[b]) a = p[a][k];
    } //now same depth
    if (a==b) return a;
    for (int k=19; k>=0; k--){
        if (p[a][k] != p[b][k]){ a=p[a][k]; b=p[b][k];}
    }
    return p[a][0];
}

void dp (int x){
    if (depth[x] <= depth[lc]) return;
    if (ans[pe[x]] == -1) bef.push_back(x);
	if (root(x) == x) dp(p[x][0]);
	else dp(root(x));
}

int main(){
    ct=1;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    memset(par,-1,sizeof(par));
    memset(is,0,sizeof(is));
    memset(ans,-1,sizeof(ans));
    cin >> n >> e;
    for (int i=1; i<=e; i++) cin >> a[i] >> b[i];
    for (int i=1; i<n; i++){
        cin >> r[i];
        is[r[i]] = 1;
        adj[a[r[i]]].push_back(make_pair(b[r[i]],r[i]));
        adj[b[r[i]]].push_back(make_pair(a[r[i]],r[i]));
    }
    depth[1] = 0;
    dfs(1,-1);
    for (int k=1; k<20; k++){
        for (int i=1; i<=n; i++){
            if (p[i][k-1] != -1){
                p[i][k] = p[p[i][k-1]][k-1];
            } else p[i][k] = -1;
        }
    } //2k decomp

    for (int i=1; i<=e; i++){
        if (ans[i] != -1) continue;
        if (is[i] && ans[i] == -1){ ans[i] = ct; ct++; continue;}
        lc = lca(a[i],b[i]);
        dp(a[i]);
        dp(b[i]);
        vector<int> edg; for (int v : bef) edg.push_back(pe[v]);
        sort(edg.begin(),edg.end());
        for (int v : edg) ans[v] = ct, ct++;
        for (int v : bef){
            par[v] = root(lc);
        }
        ans[i] = ct; ct++;
        bef.clear();
    }
    for (int i=1; i<=e; i++) cout << ans[i] << ' ';
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9932 KB Output is correct
2 Correct 7 ms 10020 KB Output is correct
3 Correct 6 ms 9932 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9932 KB Output is correct
2 Correct 7 ms 10020 KB Output is correct
3 Correct 6 ms 9932 KB Output is correct
4 Correct 6 ms 10164 KB Output is correct
5 Correct 7 ms 10060 KB Output is correct
6 Correct 6 ms 10188 KB Output is correct
7 Correct 6 ms 10060 KB Output is correct
8 Correct 6 ms 10060 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 25476 KB Output is correct
2 Correct 138 ms 31676 KB Output is correct
3 Correct 134 ms 19568 KB Output is correct
4 Correct 196 ms 53080 KB Output is correct
5 Correct 213 ms 55084 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 33876 KB Output is correct
2 Correct 95 ms 19972 KB Output is correct
3 Correct 45 ms 15052 KB Output is correct
4 Correct 98 ms 27536 KB Output is correct
5 Correct 33 ms 17224 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 56812 KB Output is correct
2 Correct 313 ms 63876 KB Output is correct
3 Correct 66 ms 25116 KB Output is correct
4 Correct 115 ms 32524 KB Output is correct
5 Correct 364 ms 67248 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 42132 KB Output is correct
2 Correct 131 ms 32212 KB Output is correct
3 Correct 391 ms 60188 KB Output is correct
4 Correct 361 ms 56652 KB Output is correct
5 Correct 25 ms 14284 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9932 KB Output is correct
2 Correct 7 ms 10020 KB Output is correct
3 Correct 6 ms 9932 KB Output is correct
4 Correct 6 ms 10164 KB Output is correct
5 Correct 7 ms 10060 KB Output is correct
6 Correct 6 ms 10188 KB Output is correct
7 Correct 6 ms 10060 KB Output is correct
8 Correct 6 ms 10060 KB Output is correct
9 Correct 75 ms 25476 KB Output is correct
10 Correct 138 ms 31676 KB Output is correct
11 Correct 134 ms 19568 KB Output is correct
12 Correct 196 ms 53080 KB Output is correct
13 Correct 213 ms 55084 KB Output is correct
14 Correct 146 ms 33876 KB Output is correct
15 Correct 95 ms 19972 KB Output is correct
16 Correct 45 ms 15052 KB Output is correct
17 Correct 98 ms 27536 KB Output is correct
18 Correct 33 ms 17224 KB Output is correct
19 Correct 272 ms 56812 KB Output is correct
20 Correct 313 ms 63876 KB Output is correct
21 Correct 66 ms 25116 KB Output is correct
22 Correct 115 ms 32524 KB Output is correct
23 Correct 364 ms 67248 KB Output is correct
24 Correct 237 ms 42132 KB Output is correct
25 Correct 131 ms 32212 KB Output is correct
26 Correct 391 ms 60188 KB Output is correct
27 Correct 361 ms 56652 KB Output is correct
28 Correct 25 ms 14284 KB Output is correct
29 Correct 498 ms 55096 KB Output is correct
30 Correct 505 ms 57064 KB Output is correct
31 Correct 456 ms 55504 KB Output is correct
32 Correct 167 ms 19656 KB Output is correct
33 Correct 389 ms 56144 KB Output is correct