oj.uz

Submission #166057

# Submission time Handle Problem Language Result Execution time Memory
166057 2019-11-30T13:40:09 Z theStaticMind Usmjeri (COCI17_usmjeri) C++14
140 / 140
 1229 ms 137568 KB 
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
//#define int long long int
using namespace std;
vector<int>adj[300005];
vector<ii>input;
map<int,int>edge[300005];
vector<ii>arr(300005);
vector<int>no(300005),path(300005,0);
vector<int>depth(300005,0),edgedepth(300005,0);
vector<vector<int>> anc(20,vector<int>(300005,0));
int lca(int x,int y){
      if(depth[x]<depth[y])swap(x,y);
      int Q=(1<<19);
      for(int w=19;w>=0;w--){
            if(depth[x]-depth[y]>=Q)
            x=anc[w][x];
            Q/=2;
      }
      if(x==y)return x;
      for(int w=19;w>=0;w--){
            if(anc[w][x]!=anc[w][y]){
                  x=anc[w][x];
                  y=anc[w][y];
            }
      }
      return anc[0][x];
}
int F(int x){
      if(no[x]==x)return x;
      return no[x]=F(no[x]);
}
bool merge(int x,int y){
      x=F(x);
      y=F(y);
      if(x==y)return false;
      if(edgedepth[x]>edgedepth[y])swap(x,y);
      no[y]=x;
      return true;
}
void dfs(int x,int pre,int d){
      depth[x]=d;
      for(int i=0;i<adj[x].size();i++){
            int y=adj[x][i];
            if(y==pre)continue;
            anc[0][y]=x;
            edgedepth[edge[x][y]]=d;
            dfs(y,x,d+1);
      }
}
int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
 //     freopen("q.gir","r",stdin);
 //     freopen("q.cik","w",stdout);
      int n,m;
      cin>>n>>m;
      for(int i=1;i<=n-1;i++)no[i]=i;
      for(int i=1;i<=n;i++)path[i]=i;
      for(int i=0;i<n-1;i++){
            int x,y;cin>>x>>y;
            adj[x].pb(y);
            adj[y].pb(x);
            edge[x][y]=i+1;
            edge[y][x]=i+1;
            arr[i+1]={x,y};
      }
      dfs(1,0,0);
      for(int d=1;d<20;d++){
            for(int x=1;x<=n;x++)anc[d][x]=anc[d-1][anc[d-1][x]];
      }
      long long int ans=1;
      for(int i=0;i<m;i++){
            int x,y;
            cin>>x>>y;
            if(depth[x]<depth[y])swap(x,y);
            input.pb({x,y});
            int l=lca(x,y);
            if(depth[path[x]]>depth[l])path[x]=l;
            if(depth[path[y]]>depth[l])path[y]=l;
      }
      for(int i=1;i<=n;i++){
            int x=i;
            if(x==path[x])continue;
            int finish=path[x];
            int last=edge[x][anc[0][x]];
            x=anc[0][x];
            while(depth[x]>depth[finish]){
                  if(merge(edge[x][anc[0][x]],last)){
                        last=edge[x][anc[0][x]];
                        x=anc[0][x];
                  }
                  else{
                        int q=arr[F(last)].first,w=arr[F(last)].second;
                        if(depth[q]<depth[w])swap(q,w);
                        last=edge[q][w];
                        x=w;
                  }
            }
      }
      for(int i=0;i<m;i++){
            int x=input[i].first,y=input[i].second;
            int l=lca(x,y);
            if(y==l)continue;
            if(F(edge[x][anc[0][x]])==F(edge[y][anc[0][y]]))ans=0;
      }
  /*    for(int i=0;i<m;i++){
            int x=input[i].first,y=input[i].second;
            int l=lca(x,y);
            if(y==l)continue;
            ///direction is ignored
      }*/
      for(int i=0;i<m;i++){
            int x=input[i].first,y=input[i].second;
            int l=lca(x,y);
            if(y==l)continue;
            merge(edge[x][anc[0][x]],edge[y][anc[0][y]]);
      }
      set<int> cnt;
      for(int i=1;i<=n-1;i++)cnt.insert(F(i));
      for(int i=0;i<cnt.size();i++)ans=(long long int)ans*2%modulo;
      cout<<ans<<endl;
}

Compilation message

usmjeri.cpp: In function 'void dfs(int, int, int)':
usmjeri.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<adj[x].size();i++){
                   ~^~~~~~~~~~~~~~
usmjeri.cpp: In function 'int32_t main()':
usmjeri.cpp:127:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<cnt.size();i++)ans=(long long int)ans*2%modulo;
                   ~^~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 80484 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 598 ms 137568 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 53240 KB Output is correct
2 Correct 54 ms 53112 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 53112 KB Output is correct
2 Correct 57 ms 53112 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 53172 KB Output is correct
2 Correct 60 ms 53112 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 53112 KB Output is correct
2 Correct 60 ms 53220 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 836 ms 105676 KB Output is correct
2 Correct 930 ms 110996 KB Output is correct
3 Correct 721 ms 89716 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1229 ms 105420 KB Output is correct
2 Correct 1116 ms 113328 KB Output is correct
3 Correct 806 ms 91496 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1111 ms 106384 KB Output is correct
2 Correct 1008 ms 111956 KB Output is correct
3 Correct 836 ms 91816 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1145 ms 106308 KB Output is correct
2 Correct 968 ms 114232 KB Output is correct
3 Correct 630 ms 85732 KB Output is correct