oj.uz

Submission #909550

# Submission time Handle Problem Language Result Execution time Memory
909550 2024-01-17T09:06:20 Z ttamx Rigged Roads (NOI19_riggedroads) C++14
58 / 100
 623 ms 262144 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=1e6+5;

int n,m;
pair<int,int> edge[N];
vector<pair<int,int>> adj[N];
int pa[N],pid[N],lv[N];
int fa[N];
int ans[N];
bool ok[N];

int fp(int u){
    return fa[u]=u==fa[u]?u:fp(fa[u]);
}

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

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        auto &[u,v]=edge[i];
        cin >> u >> v;
    }
    for(int i=1;i<=n;i++){
        int x;
        cin >> x;
        auto [u,v]=edge[x];
        adj[u].emplace_back(v,x);
        adj[v].emplace_back(u,x);
        ok[x]=true;
    }
    dfs(1);
    for(int i=1;i<=n;i++)fa[i]=i;
    int cnt=1;
    for(int i=1;i<=m;i++){
        if(ans[i])continue;
        auto [u,v]=edge[i];
        u=fp(u),v=fp(v);
        vector<int> res;
        while(u!=v){
            if(lv[u]<lv[v])swap(u,v);
            res.emplace_back(pid[u]);
            u=fa[u]=fp(pa[u]);
        }
        sort(res.begin(),res.end());
        for(auto j:res)ans[j]=cnt++;
        if(!ok[i])ans[i]=cnt++;
    }
    for(int i=1;i<=m;i++)cout << ans[i] << " ";
}

Compilation message

riggedroads.cpp: In function 'void dfs(int, int)':
riggedroads.cpp:21:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |     for(auto [v,i]:adj[u])if(v!=p){
      |              ^
riggedroads.cpp: In function 'int main()':
riggedroads.cpp:32:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |         auto &[u,v]=edge[i];
      |               ^
riggedroads.cpp:38:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |         auto [u,v]=edge[x];
      |              ^
riggedroads.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |         auto [u,v]=edge[i];
      |              ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 33116 KB Output is correct
2 Correct 9 ms 33116 KB Output is correct
3 Correct 9 ms 33112 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 33116 KB Output is correct
2 Correct 9 ms 33116 KB Output is correct
3 Correct 9 ms 33112 KB Output is correct
4 Correct 10 ms 33368 KB Output is correct
5 Correct 10 ms 33372 KB Output is correct
6 Correct 10 ms 33396 KB Output is correct
7 Correct 10 ms 33468 KB Output is correct
8 Correct 10 ms 33372 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 38600 KB Output is correct
2 Correct 67 ms 44060 KB Output is correct
3 Correct 64 ms 40144 KB Output is correct
4 Correct 114 ms 52288 KB Output is correct
5 Correct 103 ms 53320 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 45068 KB Output is correct
2 Correct 46 ms 37972 KB Output is correct
3 Correct 30 ms 35924 KB Output is correct
4 Correct 57 ms 41948 KB Output is correct
5 Correct 24 ms 36948 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 623 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 48484 KB Output is correct
2 Correct 69 ms 44152 KB Output is correct
3 Correct 335 ms 58128 KB Output is correct
4 Correct 214 ms 56144 KB Output is correct
5 Correct 23 ms 34648 KB Output is correct

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 33116 KB Output is correct
2 Correct 9 ms 33116 KB Output is correct
3 Correct 9 ms 33112 KB Output is correct
4 Correct 10 ms 33368 KB Output is correct
5 Correct 10 ms 33372 KB Output is correct
6 Correct 10 ms 33396 KB Output is correct
7 Correct 10 ms 33468 KB Output is correct
8 Correct 10 ms 33372 KB Output is correct
9 Correct 42 ms 38600 KB Output is correct
10 Correct 67 ms 44060 KB Output is correct
11 Correct 64 ms 40144 KB Output is correct
12 Correct 114 ms 52288 KB Output is correct
13 Correct 103 ms 53320 KB Output is correct
14 Correct 62 ms 45068 KB Output is correct
15 Correct 46 ms 37972 KB Output is correct
16 Correct 30 ms 35924 KB Output is correct
17 Correct 57 ms 41948 KB Output is correct
18 Correct 24 ms 36948 KB Output is correct
19 Runtime error 623 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -