oj.uz

Submission #909552

# Submission time Handle Problem Language Result Execution time Memory
909552 2024-01-17T09:07:09 Z ttamx Rigged Roads (NOI19_riggedroads) C++14
0 / 100
 917 ms 262144 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=3e5+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
0 / 8.0

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

Subtask #2
0 / 19.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 12.0

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

Subtask #7
0 / 32.0

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