QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#104323 | #6332. Two Currencies | oscaryang | 0 | 299ms | 74428kb | C++14 | 2.5kb | 2023-05-10 09:03:59 | 2023-05-10 09:04:01 |
Judging History
answer
#include<bits/stdc++.h>
#define vc vector
#define pb push_back
#define int long long
using namespace std;
const int N=1e5+5,Lim=18;
inline int read() {
int x=0,w=0; char ch=getchar();
while(!isdigit(ch)) w|=(ch=='-'), ch=getchar();
while(isdigit(ch)) x=x*10+(ch^48), ch=getchar();
return w?-x:x;
}
inline void write(int x) { if(x>9) write(x/10); putchar(x%10+'0'); }
inline void writee(int x) { write(x); putchar(10); }
int n,m,q,len,b[N];
int d[N],fa[Lim][N];
int hd[N],to[N<<1],ne[N<<1],tc=1;
vc<int> cost[N];
//sgt
int idx,rt[N],ch[N<<5][2],s[N<<5],sz[N<<5];
#define mid (l+r>>1)
#define lc(x) (ch[x][0])
#define rc(x) (ch[x][1])
inline void psu(int k) { sz[k]=sz[lc(k)]+sz[rc(k)]; s[k]=s[lc(k)]+s[rc(k)]; }
inline void ins(int &k,int pre,int l,int r,int p) {
k=++idx; lc(k)=lc(pre); rc(k)=rc(pre); s[k]=s[pre]; sz[k]=sz[pre];
if(l==r) return ++sz[k], s[k]+=b[l], void();
return (p<=mid?ins(lc(k),lc(pre),l,mid,p):ins(rc(k),rc(pre),mid+1,r,p)), psu(k);
}
inline int ask(int x,int y,int z,int l,int r,int v) {
if(l==r) return max(0ll,sz[x]+sz[y]-2*sz[z]-v/b[l]);
int res=s[lc(x)]+s[lc(y)]-2*s[lc(z)];
if(v>=res) return ask(rc(x),rc(y),rc(z),mid+1,r,v-res);
else return ask(lc(x),lc(y),lc(z),l,mid,v)+(sz[rc(x)]+sz[rc(y)]-2*sz[rc(z)]);
}
//tree
inline void add(int x,int y) {
to[++tc]=y; ne[tc]=hd[x]; hd[x]=tc;
to[++tc]=x; ne[tc]=hd[y]; hd[y]=tc;
}
inline void dfs(int x) {
for(int i=1;i<Lim;i++) fa[i][x]=fa[i-1][fa[i-1][x]];
for(int i=hd[x],y;i;i=ne[i]) if((y=to[i])!=fa[0][x]) {
fa[0][y]=x; d[y]=d[x]+1;
rt[y]=rt[x];
if(cost[i>>1].size())
for(auto u:cost[i>>1]) ins(rt[y],rt[y],1,len,u);
dfs(y);
}
}
inline int lca(int x,int y) {
if(d[x]>d[y]) swap(x,y);
for(int i=Lim-1;i>=0;i--) if(d[fa[i][x]]>=d[y]) x=fa[i][x];
if(x==y) return x;
for(int i=Lim-1;i>=0;i--) if(fa[i][x]^fa[i][y]) x=fa[i][x], y=fa[i][y];
return fa[0][x];
}
//solve
inline void solve() {
int s=read(), t=read(), x=read(), y=read();
int p=lca(s,t);
int res=ask(rt[s],rt[t],rt[p],1,len,y);
if(res>x) return puts("-1"), void();
else writee(x-res);
}
signed main() {
//freopen("a.in","r",stdin);
n=read(); m=read(); q=read(); b[++len]=0;
for(int i=1,u,v;i<n;i++) u=read(), v=read(), add(u,v);
for(int i=1,p;i<=m;i++) p=read(), b[++len]=read(), cost[p].pb(b[len]);
sort(b+1,b+1+len); len=unique(b+1,b+1+len)-b-1;
for(int i=1;i<=n;i++)
for(auto &u:cost[i]) u=lower_bound(b+1,b+1+len,u)-b;
d[1]=1; dfs(1);
while(q--) solve();
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: 6ms
memory: 6884kb
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 20 21 54569538 -1 26669081 32 255375699 -1 5 4 -1 427653834 -1 4 19 5 4 -1 -1 -1 265022184 218253041 -1 24 849614439 4 29092527 539604026 -1 -1 -1 6 -1 11 8 -1 20 -1 6 3 20 -1 -1 0 -1 546008661 4 -1 86261072 -1 448122840 873577464...
result:
wrong answer 8th numbers differ - expected: '22', found: '20'
Subtask #2:
score: 0
Wrong Answer
Test #32:
score: 0
Wrong Answer
time: 227ms
memory: 33376kb
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:
30 -1 6 53 -1 -1 652673843 -1 422622756 -1 -1 -1 23 -1 -1 -1 -1 427634455 12 265926271 263974211 877045993 2 288833077 997549690 644774220 10 995218986 25 24 924036742 5 13 -1 -1 4 -1 4393606 16 -1 932888431 991013529 8 10 -1 0 -1 5 -1 14 2 502124020 726366843 -1 18 119719836 -1 19 217737158 -1 9415...
result:
wrong answer 1st numbers differ - expected: '36', found: '30'
Subtask #3:
score: 0
Wrong Answer
Test #59:
score: 0
Wrong Answer
time: 299ms
memory: 74428kb
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:
-1 701714740 -1 610354140 816755067 -1 245932872 -1 19965 866966613 744072492 -1 -1 969398264 588051152 381506396 -1 -1 -1 -1 195466300 46790 -1 459304253 400544113 -1 787773518 -1 -1 -1 322820913 900985028 -1 -1 13283 -1 -1 -1 7592 -1 537036842 -1 261459575 84748 635912852 -1 936999022 -1 -1 -1 -1 ...
result:
wrong answer 6th numbers differ - expected: '2440', found: '-1'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%