Submission #425466

#	Time	Username	Problem	Language	Result	Execution time	Memory
425466		errorgorn	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	407 ms	42088 KiB

riggedroads

#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 (stderr)

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 / 8
• Subtask 2: 19 / 19
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 32 / 32