제출 #929619

#제출 시각아이디문제언어결과실행 시간메모리
929619ttamxUsmjeri (COCI17_usmjeri)C++14
98 / 140
1529 ms71580 KiB
#include<bits/stdc++.h> using namespace std; using t3 = tuple<int,int,int>; const int N=3e5+5; const int K=1<<20; const int MOD=1e9+7; int n,m; vector<int> adj[N]; int pa[N],lv[N],sz[N],hv[N],hd[N],disc[N]; int timer; vector<t3> qr; int ans=1; struct Node{ int mn,mx; Node():mn(0),mx(0){} Node(int x):mn(x),mx(x){} Node(int _mn,int _mx):mn(_mn),mx(_mx){} friend Node operator+(const Node &lhs,const Node &rhs){ return Node(min(lhs.mn,rhs.mn),max(lhs.mx,rhs.mx)); } Node &operator+=(const Node &rhs){ return *this=*this+rhs; } }; struct Segtree{ Node t[K],lz[K]; void push(int l,int r,int i){ t[i]+=lz[i]; if(l<r){ lz[i*2]+=lz[i]; lz[i*2+1]+=lz[i]; } lz[i]=Node(); } void update(int l,int r,int i,int x,int y,int v){ push(l,r,i); if(y<l||r<x)return; if(x<=l&&r<=y)return lz[i]=Node(v),push(l,r,i); int m=(l+r)/2; update(l,m,i*2,x,y,v); update(m+1,r,i*2+1,x,y,v); t[i]=t[i*2]+t[i*2+1]; } void update(int x,int y,int v){ update(1,n,1,x,y,v); } Node query(int l,int r,int i,int x,int y){ push(l,r,i); if(y<l||r<x)return Node(); if(x<=l&&r<=y)return t[i]; int m=(l+r)/2; return query(l,m,i*2,x,y)+query(m+1,r,i*2+1,x,y); } Node query(int x,int y){ return query(1,n,1,x,y); } }s; void dfs(int u){ sz[u]=1; for(auto v:adj[u])if(v!=pa[u]){ pa[v]=u; lv[v]=lv[u]+1; dfs(v); sz[u]+=sz[v]; if(sz[v]>sz[hv[u]])hv[u]=v; } } void hld(int u){ disc[u]=++timer; if(!hd[u])hd[u]=u; if(hv[u])hd[hv[u]]=hd[u],hld(hv[u]); for(auto v:adj[u])if(v!=pa[u]&&v!=hv[u])hld(v); } int lca(int u,int v){ while(hd[u]!=hd[v]){ if(lv[hd[u]]<lv[hd[v]])swap(u,v); u=pa[hd[u]]; } return lv[u]<lv[v]?u:v; } void update(int u,int a,int val){ while(hd[u]!=hd[a]){ s.update(disc[hd[u]],disc[u],val); u=pa[hd[u]]; } s.update(disc[a]+1,disc[u],val); } Node query(int u,int a){ Node res{}; while(hd[u]!=hd[a]){ res+=s.query(disc[hd[u]],disc[u]); u=pa[hd[u]]; } res+=s.query(disc[a]+1,disc[u]); return res; } int main(){ cin.tie(nullptr)->sync_with_stdio(false); cin >> n >> m; for(int i=1;i<n;i++){ int u,v; cin >> u >> v; adj[u].emplace_back(v); adj[v].emplace_back(u); } dfs(1); hld(1); for(int i=0;i<m;i++){ int u,v; cin >> u >> v; qr.emplace_back(lca(u,v),u,v); } sort(qr.begin(),qr.end(),[&](t3 i,t3 j){ return disc[get<0>(i)]<disc[get<0>(j)]; }); for(auto [a,u,v]:qr){ Node pu=query(u,a); Node pv=query(v,a); int mx=max(pu.mx,-pv.mn); int mn=min(pu.mn,-pv.mx); if(mx==1&&mn==-1)cout << 0,exit(0); if(mx==1){ update(u,a,1); update(v,a,-1); }else{ if(!mn){ ans*=2; if(ans>=MOD)ans-=MOD; } update(u,a,-1); update(v,a,1); } } for(int i=2;i<=n;i++){ Node tmp=s.query(i,i); if(tmp.mn&&tmp.mx)cout << 0,exit(0); if(!tmp.mn&&!tmp.mx){ ans*=2; if(ans>=MOD)ans-=MOD; } } cout << ans; }

컴파일 시 표준 에러 (stderr) 메시지

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:128:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  128 |     for(auto [a,u,v]:qr){
      |              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...