oj.uz

Submission #425466

# Submission time Handle Problem Language Result Execution time Memory
425466 2021-06-13T04:07:55 Z errorgorn Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 407 ms 42088 KB 
#include <cstdio>
#include <vector>
#include <utility>
#include <tuple>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int,int> ii;
int n,e,k;
vector<int> al[300005],temp;
vector<ii> edge;
int depth[300005],w[300005],p[300005],in[300005],father[300005];
bool tree[300005];
int parent(int i){return (p[i]==i)?i:p[i]=parent(p[i]);}
void unions(int i,int j){ //asssume i is lower than j
    i=parent(i);
    j=parent(j);
    p[i]=j;
}
void dfs(int i){
    for (vector<int>::iterator it=al[i].begin();it!=al[i].end();it++){
        if (depth[*it]==-1){
            depth[*it]=depth[i]+1;
            dfs(*it);
        }
    }
}
int main(){
    //freopen("input.txt","r",stdin);
    int a,b;
    edge.push_back(ii(0,0));
    for (int x=0;x<300005;x++){
        p[x]=x;
    }
    scanf("%d%d",&n,&e);
    for (int x=1;x<=e;x++){
        scanf("%d%d",&a,&b);
        edge.push_back(ii(a,b));
    }
    for (int x=1;x<n;x++){
        scanf("%d",&a);
        tree[a]=true;
        tie(a,b)=edge[a];
        al[a].push_back(b);
        al[b].push_back(a);
    }
    memset(depth,-1,sizeof(depth));
    depth[1]=0;
    dfs(1);
    for (int x=1;x<=e;x++){
        if (tree[x]){
            a=edge[x].first,b=edge[x].second;
            if (depth[a]<depth[b]) swap(a,b);
            in[a]=x;
            father[a]=b;
        }
    }
    for (int x=1;x<=e;x++){
        if (w[x]==0){
            a=edge[x].first,b=edge[x].second;
            a=parent(a);
            b=parent(b);
            if (!tree[x]){
                temp.clear();
                while (a!=b){
                    if (depth[a]<depth[b]) swap(a,b);
                    temp.push_back(in[a]);
                    unions(a,father[a]);
                    a=parent(a);
                }
                sort(temp.begin(),temp.end());
                for (vector<int>::iterator it=temp.begin();it!=temp.end();it++){
                    w[*it]=++k;
                }
            }
            else{
                if (a!=b){
                    if (depth[a]<depth[b]) swap(a,b);
                    unions(a,b);
                }
            }
            w[x]=++k;
        }
        printf("%d ",w[x]);
    }
}

Compilation message

riggedroads.cpp: In function 'int main()':
riggedroads.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d%d",&n,&e);
      |     ~~~~~^~~~~~~~~~~~~~
riggedroads.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~
riggedroads.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%d",&a);
      |         ~~~~~^~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 8 ms 9752 KB Output is correct
6 Correct 7 ms 9676 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 17220 KB Output is correct
2 Correct 110 ms 21408 KB Output is correct
3 Correct 109 ms 18856 KB Output is correct
4 Correct 174 ms 31556 KB Output is correct
5 Correct 187 ms 32224 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 24240 KB Output is correct
2 Correct 81 ms 16696 KB Output is correct
3 Correct 37 ms 13212 KB Output is correct
4 Correct 74 ms 20412 KB Output is correct
5 Correct 31 ms 13792 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 36516 KB Output is correct
2 Correct 274 ms 41188 KB Output is correct
3 Correct 61 ms 18360 KB Output is correct
4 Correct 104 ms 22300 KB Output is correct
5 Correct 407 ms 42088 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 28200 KB Output is correct
2 Correct 105 ms 22036 KB Output is correct
3 Correct 356 ms 36464 KB Output is correct
4 Correct 319 ms 34172 KB Output is correct
5 Correct 25 ms 11720 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 8 ms 9752 KB Output is correct
6 Correct 7 ms 9676 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 67 ms 17220 KB Output is correct
10 Correct 110 ms 21408 KB Output is correct
11 Correct 109 ms 18856 KB Output is correct
12 Correct 174 ms 31556 KB Output is correct
13 Correct 187 ms 32224 KB Output is correct
14 Correct 100 ms 24240 KB Output is correct
15 Correct 81 ms 16696 KB Output is correct
16 Correct 37 ms 13212 KB Output is correct
17 Correct 74 ms 20412 KB Output is correct
18 Correct 31 ms 13792 KB Output is correct
19 Correct 307 ms 36516 KB Output is correct
20 Correct 274 ms 41188 KB Output is correct
21 Correct 61 ms 18360 KB Output is correct
22 Correct 104 ms 22300 KB Output is correct
23 Correct 407 ms 42088 KB Output is correct
24 Correct 248 ms 28200 KB Output is correct
25 Correct 105 ms 22036 KB Output is correct
26 Correct 356 ms 36464 KB Output is correct
27 Correct 319 ms 34172 KB Output is correct
28 Correct 25 ms 11720 KB Output is correct
29 Correct 350 ms 35108 KB Output is correct
30 Correct 395 ms 35116 KB Output is correct
31 Correct 342 ms 33084 KB Output is correct
32 Correct 110 ms 18764 KB Output is correct
33 Correct 340 ms 33016 KB Output is correct