답안 #137923

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137923 2019-07-28T14:13:21 Z beso123 특수한 그래프 (IZhO13_specialg) C++14
100 / 100
536 ms 30156 KB
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int n,a[100005],pt[100005],b=0,c[100005],kd[100005],cyc[100005],bb=1,viz[100005],bebi[100005],timer=0,Size[100005],par[100005];
vector <int> g[100005],r[100005];
vector <int> starts,used,p,tin,tout,H;
vector <pii> all;
void DFS1(int v){
    used[v]=b;
    p.push_back(v);
    c[v]=p.size()-1;
    for(int k=0;k<g[v].size();k++){
        int to=g[v][k];
        if(used[to]==0)
            DFS1(to);
        else{
            if(used[to]==b){

                a[c[to]]+=bb;
                a[c[v]+1]-=bb;
                bebi[bb]=to;
                Size[bb]=c[v]-c[to]+1;
                bb++;
            }
        }
    }
}
void DFS2(int v,int h,int p){
    used[v]=1;
    H[v]=h;
    tin[v]=timer++;
    if(cyc[v]==0){
    if(cyc[p]!=0)
        pt[v]=p;
    else pt[v]=pt[p];
    }
    for(int k=0;k<r[v].size();k++){
        int to=r[v][k];
        if(used[to]==0)
            DFS2(to,h+1,v);
    }

    tout[v]=timer++;
}
void UPD(int index,int val){
    index=index+1;
    while(index<=n){
    viz[index]+=val;
    index+=index&(-index);
    }
}
int get(int index){
if(index<0)
return 0;
    int sum=0;
    index=index+1;
    while(index>0){
        sum+=viz[index];
        index-=index&(-index);
    }
    return sum;
}

bool yes(int a1,int a2){
    if(tin[a1]<=tin[a2] && tout[a1]>=tout[a2])
        return true;
    return false;
}
void ms(){
    for(int k=1;k<=n;k++)
        par[k]=k;
}
int fs(int v){
    if(par[v]==v)
        return v;
    return par[v]=fs(par[v]);
}
void us(int a1,int b1){
    a1=fs(a1);
    b1=fs(b1);
    if(a1!=b1){
        par[b1]=a1;
    }
}
int dist(int a1,int b1){
///cout<<a1<<' '<<b1<<' '<<cyc[a1]<<' '<<cyc[b1]<<' '<<yes(b1,a1)<<endl;
if(fs(a1)!=fs(b1))
    return -1;
   if(cyc[a1]==cyc[b1] && fs(a1)==fs(b1) && cyc[a1]!=0){
    if(yes(b1,a1)){
          if(c[a1]<c[b1]){

        if(get(c[b1]-1)-get(c[a1]-1)==0)
            return abs(H[a1]-H[b1]);
        else return -1;
          }
          else{
            if(get(c[b1]-1)-get(c[bebi[cyc[a1]]]-1)==0 && get(c[bebi[cyc[a1]]]+Size[cyc[a1]]-1)-get(c[a1]-1)==0){

                   return abs(H[a1]-H[b1]);
            }
        else return -1;
          }
    }

    else{
        if(c[a1]<c[b1]){
        if(get(c[b1]-1)-get(c[a1]-1)==0)
            return Size[cyc[a1]]-abs(H[a1]-H[b1]);
        else return -1;
          }
          else{
            if(get(c[b1]-1)-get(c[bebi[cyc[a1]]]-1)==0 && get(c[bebi[cyc[a1]]]+Size[cyc[a1]]-1)-get(c[a1]-1)==0)
                   return Size[cyc[a1]]-abs(H[a1]-H[b1]);
        else return -1;
          }
    }
   }
    if(fs(a1)==fs(b1)){
        if(cyc[a1]==0 && cyc[b1]!=0 && pt[a1]!=b1){
            int aa=dist(a1,pt[a1]),bb=dist(pt[a1],b1);
            if(aa!=-1 && bb!=-1)
                return aa+bb;
            else return -1;
        }
     }
    if(fs(a1)==fs(b1) && yes(b1,a1)){
        return abs(H[a1]-H[b1]);
    }
    else{
    if(fs(a1)==fs(b1)){
        if(cyc[a1]==0 && cyc[b1]!=0 && pt[a1]!=b1){

            int aa=dist(a1,pt[a1]),bb=dist(pt[a1],b1);
            if(aa!=-1 && bb!=-1)
                return aa+bb;
            else return -1;
        }
        else return 0-1;
     }
     else return -1;
    }
    return -1;
}
main(){
cin>>n;
for(int k=1;k<=n;k++){
    cin>>a[k];
    kd[k]=a[k];
    if(a[k]==0){
        starts.push_back(k);
        continue;
    }
    g[k].push_back(a[k]);
    r[a[k]].push_back(k);
    a[k]=0;
}
used.resize(n+1,0);
for(int k=1;k<=n;k++){
    if(r[k].size()==0){
            b++;
        DFS1(k);
    }
}
for(int k=1;k<=n;k++)
if(used[k]==0){
        b++;
        DFS1(k);
}
for(int k=0;k<=n;k++){
        a[k]+=a[k-1];
if(a[k]!=0){
   cyc[p[k]]=a[k];
}
}
int q;
cin>>q;
while(q--){
   int type;
   cin>>type;
   if(type==1){
    int lll;
    cin>>lll;
    if(cyc[lll]!=0){
    UPD(c[lll],1);
    }
    kd[lll]*=-1;
    all.push_back({-1,lll});
   }
   else{
    int lll,rrr;
    cin>>lll>>rrr;
    all.push_back({lll,rrr});
   }
}
for(int k=1;k<bb;k++){
starts.push_back(bebi[k]);
}
tin.resize(n+1,0);
tout.resize(n+1,0);
used.resize(0);
used.resize(n+1);
H.resize(n+1,0);
for(auto i : starts){
    DFS2(i,0,0);
}

ms();
for(int k=1;k<=n;k++){
   if(kd[k]>0)
    us(k,kd[k]);
}
vector <int> ans;
for(int k=all.size()-1;k>=0;k--){
   if(all[k].x==-1){
    int op=all[k].y;
    kd[op]*=-1;
    us(op,kd[op]);
    UPD(c[op],-1);
   }
   else{
    int a1=all[k].x,b1=all[k].y;
    ans.push_back(dist(a1,b1));
   }
}
reverse(ans.begin(),ans.end());
for(auto i : ans)
    cout<<i<<endl;
return 0;
}
/*
10
2 3 4 5 6 1 5 2 8 8
6
1 4
1 5
2 9 1
2 10 4
2 1 5
2 7 1
*/

Compilation message

specialg.cpp: In function 'void DFS1(long long int)':
specialg.cpp:15:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=0;k<g[v].size();k++){
                 ~^~~~~~~~~~~~
specialg.cpp: In function 'void DFS2(long long int, long long int, long long int)':
specialg.cpp:40:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=0;k<r[v].size();k++){
                 ~^~~~~~~~~~~~
specialg.cpp: At global scope:
specialg.cpp:148:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 5496 KB Output is correct
2 Correct 18 ms 5496 KB Output is correct
3 Correct 20 ms 5496 KB Output is correct
4 Correct 41 ms 5640 KB Output is correct
5 Correct 24 ms 5496 KB Output is correct
6 Correct 83 ms 6280 KB Output is correct
7 Correct 85 ms 6400 KB Output is correct
8 Correct 85 ms 6380 KB Output is correct
9 Correct 83 ms 6400 KB Output is correct
10 Correct 85 ms 6512 KB Output is correct
11 Correct 494 ms 29920 KB Output is correct
12 Correct 466 ms 19900 KB Output is correct
13 Correct 488 ms 23292 KB Output is correct
14 Correct 459 ms 18708 KB Output is correct
15 Correct 467 ms 20456 KB Output is correct
16 Correct 464 ms 19992 KB Output is correct
17 Correct 522 ms 26832 KB Output is correct
18 Correct 514 ms 26884 KB Output is correct
19 Correct 536 ms 26860 KB Output is correct
20 Correct 495 ms 30156 KB Output is correct