oj.uz

Submission #227860

# Submission time Handle Problem Language Result Execution time Memory
227860 2020-04-29T04:47:13 Z Autoratch Rigged Roads (NOI19_riggedroads) C++14
19 / 100
 330 ms 58220 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 1;
const int K = 20;

int n,m;
vector<pair<int,int> > adj[N];
pair<int,int> ed[N];
int pa[N],dp[K][N],id[N],lv[N];
int now,ans[N];
vector<int> res;
bool rigged[N];

void dfs(int u,int p,int t)
{
    dp[0][u] = pa[u] = p,id[u] = t,lv[u] = lv[p]+1;
    for(auto [t,v] : adj[u]) if(v!=p) dfs(v,u,t);
}

int lca(int a,int b)
{
    if(lv[a]<lv[b]) swap(a,b);
    for(int i = K-1;i >= 0;i--) if(lv[dp[i][a]]>=lv[b]) a = dp[i][a];
    if(a==b) return a;
    for(int i = K-1;i >= 0;i--) if(dp[i][a]!=dp[i][b]) a = dp[i][a],b = dp[i][b];
    return dp[0][a];
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m;
    for(int i = 1;i <= m;i++) cin >> ed[i].first >> ed[i].second;
    for(int i = 0;i < n-1;i++)
    { 
        int x; cin >> x; 
        rigged[x] = true; 
        adj[ed[x].first].push_back({x,ed[x].second}),adj[ed[x].second].push_back({x,ed[x].first}); 
    }
    dfs(1,0,0);
    for(int i = 1;i < K;i++) for(int j = 1;j <= n;j++) dp[i][j] = dp[i-1][dp[i-1][j]];
    for(int i = 1;i <= m;i++) if(!ans[i])
    {
        if(rigged[i]) 
        {
            ans[i] = ++now;
            int a = ed[i].first,b = ed[i].second;
            if(lv[a]>lv[b]) swap(a,b);
            id[b] = id[a],pa[b] = pa[a];
        }
        else
        {
            int a = ed[i].first,b = ed[i].second,aa = a,bb = b;
            int l = lca(a,b);
            res.clear();
            while(lv[pa[a]]>=lv[l]) res.push_back(id[a]),a = pa[a];
            while(lv[pa[b]]>=lv[l]) res.push_back(id[b]),b = pa[b];
            assert(id[a]==id[b] and pa[a]==pa[b]);
            id[aa] = id[bb] = id[a],pa[aa] = pa[bb] = pa[a];
            sort(res.begin(),res.end());
            for(int x : res) ans[x] = ++now;
            ans[i] = ++now;
        }
    }
    for(int i = 1;i <= m;i++) cout << ans[i] << ' ';
}

Compilation message

riggedroads.cpp: In function 'void dfs(int, int, int)':
riggedroads.cpp:18:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for(auto [t,v] : adj[u]) if(v!=p) dfs(v,u,t);
              ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7552 KB Output is correct
2 Correct 9 ms 7552 KB Output is correct
3 Incorrect 8 ms 7552 KB Output isn't correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7552 KB Output is correct
2 Correct 9 ms 7552 KB Output is correct
3 Incorrect 8 ms 7552 KB Output isn't correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 22508 KB Output is correct
2 Correct 216 ms 28016 KB Output is correct
3 Correct 218 ms 16076 KB Output is correct
4 Correct 176 ms 48224 KB Output is correct
5 Correct 204 ms 50140 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 111 ms 55284 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 49112 KB Output is correct
2 Correct 280 ms 54892 KB Output is correct
3 Correct 64 ms 21236 KB Output is correct
4 Correct 107 ms 27640 KB Output is correct
5 Correct 330 ms 58220 KB Output is correct

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 190 ms 36080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7552 KB Output is correct
2 Correct 9 ms 7552 KB Output is correct
3 Incorrect 8 ms 7552 KB Output isn't correct