Submission #295336

#	Time	Username	Problem	Language	Result	Execution time	Memory
295336		beso123	Rigged Roads (NOI19_riggedroads)	C++14	100 / 100	1274 ms	85720 KiB

riggedroads

#include <bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
const int N=300005;
int n,timer=1,lg=20,tin[N],p[N],m,t=1,ans[N],yes[N],tout[N],used[N];
vector<pii> ed;
vector<int> g[N],dp[N];
int nom[N];
void DFS(int v,int p){
    used[v]=1;
    dp[v][0]=p;
    for(int k=1;k<=19;k++)
        dp[v][k]=dp[dp[v][k-1]][k-1];
        tin[v]=timer++;
    for(int k=0;k<g[v].size();k++){
        int to=g[v][k];
        if(used[to]==0)
            DFS(to,v);
    }
    tout[v]=timer++;
}
bool tree(int a,int b){
    if(tin[a]<=tin[b] && tout[a]>=tout[b])
        return true;
     return false;
}
int LCA(int a,int b){
    if(tree(a,b)) return a;
    if(tree(b,a)) return b;
    int t=a;
    for(int k=19;k>=0;k--){
        if(dp[t][k]!=0){
        int to=dp[t][k];
        if(!tree(to,b))
            t=to;
    }
}
    return dp[t][0];
}
int FS(int v){
    if(v==p[v]) return v;
    return p[v]=FS(p[v]);
}
void US(int a,int b){
    a=FS(a);
    b=FS(b);
    if(a!=b){
        if(tree(b,a))
           swap(a,b);
        p[b]=a;
    }
    a=FS(a);
    b=FS(b);
}
main(){
cin>>n>>m;
for(int k=1;k<=m;k++){
    int a,b;
    cin>>a>>b;
    ed.push_back({a,b});
}
vector<int> op;
for(int k=1;k<n;k++){
    int a;
   cin>>a;
    a--;
    op.push_back(a);
    yes[a]=1;
    g[ed[a].x].push_back(ed[a].y);
    g[ed[a].y].push_back(ed[a].x);
}
for(int k=0;k<=n;k++){
    dp[k].resize(lg+1,0);
    p[k]=k;
}
    DFS(1,0);
for(int k=0;k<op.size();k++){
    int a=ed[op[k]].x,b=ed[op[k]].y;
    if(tree(b,a))
        swap(a,b);
    nom[b]=op[k];
}

for(int k=0;k<m;k++){
   if(ans[k]==0){
   if(yes[k]){
    US(ed[k].x,ed[k].y);
    ans[k]=t;
   }
   else{
    int a=ed[k].x,b=ed[k].y;
    int lc=LCA(a,b);
   set<int> v;
    while(FS(lc)!=FS(b) || FS(lc)!=FS(a)){
      if(FS(lc)!=FS(a)){
          int lo=nom[a];
          if(!ans[lo])
        v.insert(lo);
        US(a,dp[a][0]);
        a=FS(a);
       }
    if(FS(lc)!=FS(b)){
        int lo=nom[b];
        if(!ans[lo])
        v.insert(lo);
        US(b,dp[b][0]);
        b=FS(b);
       }
    }
 for(auto i : v){
    ans[i]=t;
    t++;
     }
 ans[k]=t;
   }
   t++;
   }
   cout<<ans[k]<<' ';
}
return 0;
}

Compilation message (stderr)

riggedroads.cpp: In function 'void DFS(int, int)':
riggedroads.cpp:14:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   14 |     for(int k=1;k<=19;k++)
      |     ^~~
riggedroads.cpp:16:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   16 |         tin[v]=timer++;
      |         ^~~
riggedroads.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int k=0;k<g[v].size();k++){
      |                 ~^~~~~~~~~~~~
riggedroads.cpp: At global scope:
riggedroads.cpp:57:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   57 | main(){
      |      ^
riggedroads.cpp: In function 'int main()':
riggedroads.cpp:79:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 | for(int k=0;k<op.size();k++){
      |             ~^~~~~~~~~~

• 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