| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 929747 |
2024-02-18T07:50:05 Z |
ttamx |
Usmjeri (COCI17_usmjeri) |
C++14 |
|
1633 ms |
109992 KB |
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
const int K=1<<20;
const int LG=19;
const int MOD=1e9+7;
int n,m;
vector<int> adj[N],adj2[N];
int pa[N][LG],lv[N],sz[N],hv[N],hd[N],disc[N];
bool vis[N],vis2[N],vis3[N];
int qu[N],qv[N],a[N],qqu[N],qqv[N];
int timer;
vector<int> qr[N];
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,int p=0){
sz[u]=1;
for(auto v:adj[u])if(v!=p){
pa[v][0]=u;
for(int i=1;i<LG;i++)pa[v][i]=pa[pa[v][i-1]][i-1];
lv[v]=lv[u]+1;
dfs(v,u);
sz[u]+=sz[v];
if(sz[v]>sz[hv[u]])hv[u]=v;
}
}
void hld(int u,int p=0){
disc[u]=++timer;
if(!hd[u])hd[u]=u;
if(hv[u])hd[hv[u]]=hd[u],hld(hv[u],u);
for(auto v:adj[u])if(v!=p&&v!=hv[u])hld(v,u);
}
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]][0];
}
return lv[u]<lv[v]?u:v;
}
int jump(int u,int tar){
for(int i=LG-1;i>=0;i--)if(lv[pa[u][i]]>=tar)u=pa[u][i];
return u;
}
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]][0];
}
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]][0];
}
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=1;i<=m;i++){
cin >> qu[i] >> qv[i];
a[i]=lca(qu[i],qv[i]);
qr[a[i]].emplace_back(i);
if(lv[qu[i]]>lv[a[i]])adj2[qqu[i]=jump(qu[i],lv[a[i]]+1)].emplace_back(i);
if(lv[qv[i]]>lv[a[i]])adj2[qqv[i]=jump(qv[i],lv[a[i]]+1)].emplace_back(i);
}
queue<int> q;
q.emplace(1);
vis[1]=true;
while(!q.empty()){
int an=q.front();
q.pop();
for(auto v:adj[an])if(!vis[v]){
vis[v]=true;
q.emplace(v);
}
function<void(int)> solve=[&](int i){
if(vis2[i])return;
vis2[i]=true;
int u=qu[i],v=qv[i];
Node pu=query(u,an);
Node pv=query(v,an);
int mx=max(pu.mx,-pv.mn);
int mn=min(pu.mn,-pv.mx);
if(mx&&mn)cout << 0,exit(0);
if(mx){
update(u,an,1);
update(v,an,-1);
}else{
if(!mn){
ans*=2;
if(ans>=MOD)ans-=MOD;
}
update(u,an,-1);
update(v,an,1);
}
if(!vis3[qqu[i]]){
vis3[qqu[i]]=true;
for(auto x:adj2[qqu[i]])solve(x);
}
if(!vis3[qqv[i]]){
vis3[qqv[i]]=true;
for(auto x:adj2[qqv[i]])solve(x);
}
};
for(auto i:qr[an])solve(i);
}
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
527 ms |
73072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
988 ms |
109992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
50464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
50424 KB |
Output is correct |
| 2 |
Correct |
13 ms |
50316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
50528 KB |
Output is correct |
| 2 |
Correct |
15 ms |
50520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
50776 KB |
Output is correct |
| 2 |
Correct |
12 ms |
50588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1626 ms |
86568 KB |
Output is correct |
| 2 |
Correct |
1633 ms |
86516 KB |
Output is correct |
| 3 |
Correct |
542 ms |
73848 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1577 ms |
87668 KB |
Output is correct |
| 2 |
Correct |
1538 ms |
87664 KB |
Output is correct |
| 3 |
Correct |
1239 ms |
74736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1436 ms |
88000 KB |
Output is correct |
| 2 |
Correct |
1547 ms |
86908 KB |
Output is correct |
| 3 |
Correct |
999 ms |
75564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1559 ms |
87344 KB |
Output is correct |
| 2 |
Correct |
1628 ms |
87384 KB |
Output is correct |
| 3 |
Correct |
221 ms |
73220 KB |
Output is correct |
