Submission #166044

#	Time	Username	Problem	Language	Result	Execution time	Memory
166044		theStaticMind	Usmjeri (COCI17_usmjeri)	C++14	0 / 140	2102 ms	157168 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<int>no(300005),direct(300005,-1);
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=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;
            input.pb({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);
            int last=edge[{x,anc[0][x]}];
            int l=lca(x,y);
            x=anc[0][x];
            while(x!=l){
                  merge(last,edge[{x,anc[0][x]}]);
                  last=edge[{x,anc[0][x]}];
                  x=anc[0][x];
            }
            if(y==l)continue;
            last=edge[{y,anc[0][y]}];
            y=anc[0][y];
            while(l!=y){
                  merge(last,edge[{y,anc[0][y]}]);
                  last=edge[{y,anc[0][y]}];
                  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;
}

Compilation message (stderr)

usmjeri.cpp: In function 'void dfs(long long int, long long int, long long int)':
usmjeri.cpp:45: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:97: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: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14