Submission #166056

#	Time	Username	Problem	Language	Result	Execution time	Memory
166056		theStaticMind	Usmjeri (COCI17_usmjeri)	C++14	84 / 140	2059 ms	173744 KiB

usmjeri

#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<ii,int> edge;
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);
      while(depth[x]!=depth[y]){
            x=anc[log2(depth[x]-depth[y])][x];
      }
      if(x==y)return x;
      while(anc[0][x]!=anc[0][y]){
            int w=19;
            while(anc[w][x]==anc[w][y])w--;
            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]];
      }
      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=ans*2%modulo;
      cout<<ans<<endl;
}

Compilation message (stderr)

usmjeri.cpp: In function 'void dfs(long long int, long long int, long long int)':
usmjeri.cpp:46: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:124:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<cnt.size();i++)ans=ans*2%modulo;
                   ~^~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14