QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#111444 | #6332. Two Currencies | Flamire | 0 | 214ms | 71912kb | C++14 | 2.2kb | 2023-06-07 08:53:58 | 2023-06-07 08:54:02 |
Judging History
answer
#include <bits/stdc++.h>
#define N 100011
#define ll long long
using namespace std;
int n,m,q,fa[N][21],ndE[N],dep[N],rt[N],sz,U[N],V[N];vector<int> w[N];
vector<int> G[N];
int lca(int u,int v)
{
if(dep[u]<dep[v])swap(u,v);for(int i=20;~i;--i)if(dep[u]-(1<<i)>=dep[v])u=fa[u][i];if(u==v)return u;
for(int i=20;~i;--i)if(fa[u][i]^fa[v][i])u=fa[u][i],v=fa[v][i];return fa[u][0];
}
ll sum[N*50],dis[N];int lc[N*50],rc[N*50],cnt[N*50];
void pushup(int x){sum[x]=sum[lc[x]]+sum[rc[x]];cnt[x]=cnt[lc[x]]+cnt[rc[x]];}
void add(int k,ll v,int L,int R,int x,int &c)
{
if(!c)c=++sz;if(L==R){sum[c]=sum[x]+v;cnt[c]=cnt[x]+1;return;}
if(k<=L+R>>1)rc[c]=rc[x],add(k,v,L,L+R>>1,lc[x],lc[c]);else lc[c]=lc[x],add(k,v,(L+R>>1)+1,R,rc[x],rc[c]);pushup(c);
}
int bin(int r1,int r2,int r3,int r4,ll v,int L,int R)
{
if(L==R)return L;
if(sum[rc[r1]]+sum[rc[r2]]-sum[rc[r3]]-sum[rc[r4]]>v)return bin(rc[r1],rc[r2],rc[r3],rc[r4],v,(L+R>>1)+1,R);
else return bin(lc[r1],lc[r2],lc[r3],lc[r4],v-(sum[rc[r1]]+sum[rc[r2]]-sum[rc[r3]]-sum[rc[r4]]),L,L+R>>1);
}
int query(int l,int r,int L,int R,int x)
{
if(!x)return 0;if(l<=L&&R<=r)return cnt[x];int ans=0;
if(l<=L+R>>1)ans+=query(l,r,L,L+R>>1,lc[x]);if(r>L+R>>1)ans+=query(l,r,(L+R>>1)+1,R,rc[x]);return ans;
}
void dfs(int u,int f)
{
fa[u][0]=f;for(int i=1;i<=20;++i)fa[u][i]=fa[fa[u][i-1]][i-1];dep[u]=dep[f]+1;
for(int v:G[u])if(v^f)dfs(v,u);
}
void dfs_(int u,int f)
{
int lst=rt[f];
for(int x:w[u])add(x,x,1,1e9,lst,rt[u]),lst=rt[u];dis[u]=dis[f];for(int x:w[u])dis[u]+=x;
for(int v:G[u])if(v^f)dfs_(v,u);
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<n;++i){int u,v;scanf("%d%d",&u,&v);G[u].push_back(v);G[v].push_back(u);U[i]=u;V[i]=v;}
dfs(1,0);
for(int i=1;i<n;++i)if(dep[U[i]]<dep[V[i]])ndE[i]=V[i];else ndE[i]=U[i];
for(int i=1;i<=m;++i){int p,c;scanf("%d%d",&p,&c);w[ndE[p]].push_back(c);}
dfs_(1,0);
while(q--)
{
int s,t,x;ll y;scanf("%d%d%d%lld",&s,&t,&x,&y);
int l=lca(s,t);ll Dis=dis[s]+dis[t]-dis[l]-dis[l];
int id=bin(rt[s],rt[t],rt[l],rt[l],Dis-y-1,1,1e9);
int num=query(id,1e9,1,1e9,rt[s])+query(id,1e9,1,1e9,rt[t])-2*query(id,1e9,1,1e9,rt[l]);
if(num>x)printf("-1\n");else printf("%d\n",x-num);
}return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 13116kb
input:
1831 1865 1153 832 1698 1672 1619 634 920 328 1244 571 1279 1673 1815 1098 92 1320 432 244 636 991 1446 308 569 1118 1356 1733 71 497 1679 1699 635 1254 1295 853 345 364 1396 1183 1134 524 1557 1642 1262 1767 459 918 794 1644 539 902 1046 334 1789 1691 1548 1298 520 1763 216 1161 1065 682 1167 1282 ...
output:
378730605 649537044 339843141 362013697 600127619 123276007 749019778 32 13 54569538 9 26669081 33 255375699 4 8 6 4 427653834 15 -1 26 11 9 -1 15 18 265022184 218253041 -1 24 849614439 11 29092527 539604026 13 18 -1 21 5 12 11 -1 21 -1 16 14 41 19 4 2 3 546008661 9 15 86261072 -1 448122840 87357746...
result:
wrong answer 8th numbers differ - expected: '22', found: '32'
Subtask #2:
score: 0
Wrong Answer
Test #32:
score: 0
Wrong Answer
time: 214ms
memory: 61404kb
input:
99819 89735 60985 59741 24953 61387 12293 53761 1828 60970 60534 40598 48807 21876 21232 29527 13335 84269 40756 89571 12996 25757 40587 52477 63347 41372 69243 16391 58678 40854 39513 84384 91744 62938 60371 81932 45504 34121 54746 51945 14294 883 85344 78845 51797 45025 76590 37694 65493 4118 2588...
output:
53 -1 24 44 14 13 652673843 19 422622756 3 9 -1 29 -1 3 16 23 427634455 34 265926271 263974211 877045993 15 288833077 997549690 644774220 10 995218986 27 30 924036742 33 18 13 4 9 -1 4393606 19 11 932888431 991013529 21 15 4 9 17 28 9 31 9 502124020 726366843 10 20 119719836 6 37 217737158 1 9415918...
result:
wrong answer 1st numbers differ - expected: '36', found: '53'
Subtask #3:
score: 0
Wrong Answer
Test #59:
score: 0
Wrong Answer
time: 187ms
memory: 71912kb
input:
95629 64841 64314 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51...
output:
8134 701714740 22117 610354140 816755067 9110 245932872 4006 40385 866966613 744072492 1428 26112 969398264 588051152 381506396 4720 7219 10856 53274 195466300 68362 956 459304253 400544113 13586 787773518 4202 13225 9102 322820913 900985028 14008 29635 27054 16697 40829 25336 14887 8214 537036842 3...
result:
wrong answer 1st numbers differ - expected: '-1', found: '8134'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%