oj.uz

Submission #750510

# Submission time Handle Problem Language Result Execution time Memory
750510 2023-05-29T15:18:18 Z bachhoangxuan Two Currencies (JOI23_currencies) C++17
100 / 100
 3123 ms 128272 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define fi first
#define se second
const int inf=1e18;
const int mod=998244353;
const int mod2=1e9+7;
const int maxn=100005;
const int bl=650;
const int maxs=650;
const int maxm=200005;
const int maxq=500005;
const int maxl=20;
const int maxa=1000005;
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
struct ask{
    int s,t,x,y,id;
};
namespace Segtree{
    int val[4*maxn],num[4*maxn];
    void pushdown(int id){
        val[id<<1]+=val[id];num[id<<1]+=num[id];
        val[id<<1|1]+=val[id];num[id<<1|1]+=num[id];
        val[id]=num[id]=0;
    }
    void update(int l,int r,int id,int tl,int tr,int x,int y){
        if(tr<l || r<tl) return;
        if(tl<=l && r<=tr){
            val[id]+=x;num[id]+=y;
            return;
        }
        pushdown(id);
        int mid=(l+r)>>1;
        update(l,mid,id<<1,tl,tr,x,y);update(mid+1,r,id<<1|1,tl,tr,x,y);
    }
    pii query(int l,int r,int id,int p){
        if(l==r) return {val[id],num[id]};
        pushdown(id);
        int mid=(l+r)>>1;
        if(p<=mid) return query(l,mid,id<<1,p);
        else return query(mid+1,r,id<<1|1,p);
    }
}
int n,m,q,L[maxn],R[maxn],res[maxn],a[maxn],b[maxn],pos,dep[maxn];
int parent[maxn][maxl];
vector<int> edge[maxn];
vector<ask> query[maxn];
vector<pii> cp;
void add(pii p,int t){
    Segtree::update(1,n,1,L[b[p.se]],R[b[p.se]],p.fi*t,t);
}
void dfs(int u,int par){
    //cout << u << ' ' << par << '\n';
    L[u]=++pos;parent[u][0]=par;dep[u]=dep[par]+1;
    for(int v:edge[u]){
        if(v==par) continue;
        dfs(v,u);
    }
    R[u]=pos;
}
int lca(int u,int v){
    if(dep[u]>dep[v]) swap(u,v);
    for(int i=0;i<=18;i++){
        if((dep[v]-dep[u])&(1<<i)) v=parent[v][i];
    }
    if(u==v) return u;
    for(int i=18;i>=0;i--){
        if(parent[u][i]!=parent[v][i]){
            u=parent[u][i];
            v=parent[v][i];
        }
    }
    return parent[u][0];
}
void build_tree(){
    dfs(1,0);
    for(int i=1;i<=18;i++){
        for(int j=1;j<=n;j++) parent[j][i]=parent[parent[j][i-1]][i-1];
    }
}
pii cal(int x,int y){
    int p=lca(x,y);
    //cout << x << ' ' << y << ' ' << p << '\n';
    pii fx=Segtree::query(1,n,1,L[x]),fy=Segtree::query(1,n,1,L[y]),fp=Segtree::query(1,n,1,L[p]);
    return {fx.fi+fy.fi-2*fp.fi,fx.se+fy.se-2*fp.se};
}
void dnc(int l,int r){
    int mid=(l+r)>>1,mid1=(l+mid-1)>>1,mid2=(mid+1+r)>>1;
    for(ask d:query[mid]){
        pii ans=cal(d.s,d.t);
        //cout << mid << ' ' << d.x << ' ' << d.y << '\n';
        if(ans.fi<=d.x){
            res[d.id]=ans.se;
            if(mid<r) query[mid2].push_back(d);
        }
        else if(l<mid) query[mid1].push_back(d);
    }
    if(l<mid){
        for(int i=mid;i>mid1;i--) add(cp[i],-1);
        dnc(l,mid-1);
        for(int i=mid1+1;i<=mid;i++) add(cp[i],1);
    }
    if(mid<r){
        for(int i=mid+1;i<=mid2;i++) add(cp[i],1);
        dnc(mid+1,r);
        for(int i=mid2;i>mid;i--) add(cp[i],-1);
    }
}
void solve(){
    cin >> n >> m >> q;
    for(int i=1;i<n;i++){
        cin >> a[i] >> b[i];
        edge[a[i]].push_back(b[i]);
        edge[b[i]].push_back(a[i]);
    }
    build_tree();
    for(int i=1;i<=m;i++){
        int p,c;cin >> p >> c;
        cp.push_back({c,p});
        if(L[a[p]]>L[b[p]]) swap(a[p],b[p]);
    }
    sort(cp.begin(),cp.end());
    int mid=(m-1)>>1;
    for(int i=1;i<=q;i++){
        res[i]=0;
        int s,t,x,y;cin >> s >> t >> y >> x;
        query[mid].push_back({s,t,x,y,i});
    }
    for(int i=0;i<=mid;i++) add(cp[i],1);
    dnc(0,m-1);
    for(int i=mid+1;i<m;i++) add(cp[i],1);
    for(ask d:query[mid]){
        pii ans=cal(d.s,d.t);
        res[d.id]=ans.se-res[d.id];
        if(res[d.id]>d.y) res[d.id]=-1;
        else res[d.id]=d.y-res[d.id];
    }
    for(int i=1;i<=q;i++) cout << res[i] << '\n';
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 13 ms 6316 KB Output is correct
6 Correct 16 ms 6708 KB Output is correct
7 Correct 14 ms 6484 KB Output is correct
8 Correct 17 ms 6888 KB Output is correct
9 Correct 17 ms 6832 KB Output is correct
10 Correct 19 ms 6868 KB Output is correct
11 Correct 16 ms 6772 KB Output is correct
12 Correct 17 ms 6820 KB Output is correct
13 Correct 17 ms 6868 KB Output is correct
14 Correct 17 ms 6900 KB Output is correct
15 Correct 20 ms 6876 KB Output is correct
16 Correct 20 ms 6868 KB Output is correct
17 Correct 20 ms 6864 KB Output is correct
18 Correct 20 ms 6904 KB Output is correct
19 Correct 16 ms 6868 KB Output is correct
20 Correct 17 ms 6780 KB Output is correct
21 Correct 16 ms 6888 KB Output is correct
22 Correct 15 ms 6844 KB Output is correct
23 Correct 15 ms 6868 KB Output is correct
24 Correct 18 ms 6964 KB Output is correct
25 Correct 15 ms 6868 KB Output is correct
26 Correct 12 ms 6740 KB Output is correct
27 Correct 12 ms 6808 KB Output is correct
28 Correct 14 ms 6824 KB Output is correct
29 Correct 16 ms 6740 KB Output is correct
30 Correct 18 ms 6868 KB Output is correct
31 Correct 17 ms 6892 KB Output is correct
32 Correct 16 ms 6832 KB Output is correct
33 Correct 16 ms 6936 KB Output is correct
34 Correct 17 ms 6832 KB Output is correct
35 Correct 15 ms 6796 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 18 ms 6828 KB Output is correct
3 Correct 22 ms 6764 KB Output is correct
4 Correct 17 ms 6756 KB Output is correct
5 Correct 1473 ms 87660 KB Output is correct
6 Correct 1780 ms 110260 KB Output is correct
7 Correct 2117 ms 106696 KB Output is correct
8 Correct 1464 ms 87028 KB Output is correct
9 Correct 1407 ms 82848 KB Output is correct
10 Correct 1932 ms 120648 KB Output is correct
11 Correct 2214 ms 120296 KB Output is correct
12 Correct 1927 ms 120132 KB Output is correct
13 Correct 1836 ms 120376 KB Output is correct
14 Correct 2154 ms 119880 KB Output is correct
15 Correct 3026 ms 124948 KB Output is correct
16 Correct 2670 ms 125584 KB Output is correct
17 Correct 2763 ms 124992 KB Output is correct
18 Correct 2901 ms 122352 KB Output is correct
19 Correct 2785 ms 122380 KB Output is correct
20 Correct 2705 ms 123012 KB Output is correct
21 Correct 1526 ms 124792 KB Output is correct
22 Correct 1469 ms 125600 KB Output is correct
23 Correct 1881 ms 125588 KB Output is correct
24 Correct 1717 ms 125244 KB Output is correct
25 Correct 1922 ms 117904 KB Output is correct
26 Correct 1938 ms 117024 KB Output is correct
27 Correct 1986 ms 119384 KB Output is correct
28 Correct 1139 ms 110600 KB Output is correct
29 Correct 1226 ms 109488 KB Output is correct
30 Correct 1225 ms 110476 KB Output is correct
31 Correct 1254 ms 109852 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 18 ms 6840 KB Output is correct
3 Correct 23 ms 6884 KB Output is correct
4 Correct 25 ms 6808 KB Output is correct
5 Correct 1865 ms 92264 KB Output is correct
6 Correct 1820 ms 93100 KB Output is correct
7 Correct 2058 ms 97504 KB Output is correct
8 Correct 2479 ms 126044 KB Output is correct
9 Correct 2724 ms 125544 KB Output is correct
10 Correct 2548 ms 126140 KB Output is correct
11 Correct 1728 ms 126196 KB Output is correct
12 Correct 1636 ms 126160 KB Output is correct
13 Correct 1646 ms 126032 KB Output is correct
14 Correct 966 ms 126736 KB Output is correct
15 Correct 948 ms 128272 KB Output is correct
16 Correct 1058 ms 126904 KB Output is correct
17 Correct 1138 ms 127344 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 13 ms 6316 KB Output is correct
6 Correct 16 ms 6708 KB Output is correct
7 Correct 14 ms 6484 KB Output is correct
8 Correct 17 ms 6888 KB Output is correct
9 Correct 17 ms 6832 KB Output is correct
10 Correct 19 ms 6868 KB Output is correct
11 Correct 16 ms 6772 KB Output is correct
12 Correct 17 ms 6820 KB Output is correct
13 Correct 17 ms 6868 KB Output is correct
14 Correct 17 ms 6900 KB Output is correct
15 Correct 20 ms 6876 KB Output is correct
16 Correct 20 ms 6868 KB Output is correct
17 Correct 20 ms 6864 KB Output is correct
18 Correct 20 ms 6904 KB Output is correct
19 Correct 16 ms 6868 KB Output is correct
20 Correct 17 ms 6780 KB Output is correct
21 Correct 16 ms 6888 KB Output is correct
22 Correct 15 ms 6844 KB Output is correct
23 Correct 15 ms 6868 KB Output is correct
24 Correct 18 ms 6964 KB Output is correct
25 Correct 15 ms 6868 KB Output is correct
26 Correct 12 ms 6740 KB Output is correct
27 Correct 12 ms 6808 KB Output is correct
28 Correct 14 ms 6824 KB Output is correct
29 Correct 16 ms 6740 KB Output is correct
30 Correct 18 ms 6868 KB Output is correct
31 Correct 17 ms 6892 KB Output is correct
32 Correct 16 ms 6832 KB Output is correct
33 Correct 16 ms 6936 KB Output is correct
34 Correct 17 ms 6832 KB Output is correct
35 Correct 15 ms 6796 KB Output is correct
36 Correct 3 ms 5076 KB Output is correct
37 Correct 18 ms 6828 KB Output is correct
38 Correct 22 ms 6764 KB Output is correct
39 Correct 17 ms 6756 KB Output is correct
40 Correct 1473 ms 87660 KB Output is correct
41 Correct 1780 ms 110260 KB Output is correct
42 Correct 2117 ms 106696 KB Output is correct
43 Correct 1464 ms 87028 KB Output is correct
44 Correct 1407 ms 82848 KB Output is correct
45 Correct 1932 ms 120648 KB Output is correct
46 Correct 2214 ms 120296 KB Output is correct
47 Correct 1927 ms 120132 KB Output is correct
48 Correct 1836 ms 120376 KB Output is correct
49 Correct 2154 ms 119880 KB Output is correct
50 Correct 3026 ms 124948 KB Output is correct
51 Correct 2670 ms 125584 KB Output is correct
52 Correct 2763 ms 124992 KB Output is correct
53 Correct 2901 ms 122352 KB Output is correct
54 Correct 2785 ms 122380 KB Output is correct
55 Correct 2705 ms 123012 KB Output is correct
56 Correct 1526 ms 124792 KB Output is correct
57 Correct 1469 ms 125600 KB Output is correct
58 Correct 1881 ms 125588 KB Output is correct
59 Correct 1717 ms 125244 KB Output is correct
60 Correct 1922 ms 117904 KB Output is correct
61 Correct 1938 ms 117024 KB Output is correct
62 Correct 1986 ms 119384 KB Output is correct
63 Correct 1139 ms 110600 KB Output is correct
64 Correct 1226 ms 109488 KB Output is correct
65 Correct 1225 ms 110476 KB Output is correct
66 Correct 1254 ms 109852 KB Output is correct
67 Correct 3 ms 5076 KB Output is correct
68 Correct 18 ms 6840 KB Output is correct
69 Correct 23 ms 6884 KB Output is correct
70 Correct 25 ms 6808 KB Output is correct
71 Correct 1865 ms 92264 KB Output is correct
72 Correct 1820 ms 93100 KB Output is correct
73 Correct 2058 ms 97504 KB Output is correct
74 Correct 2479 ms 126044 KB Output is correct
75 Correct 2724 ms 125544 KB Output is correct
76 Correct 2548 ms 126140 KB Output is correct
77 Correct 1728 ms 126196 KB Output is correct
78 Correct 1636 ms 126160 KB Output is correct
79 Correct 1646 ms 126032 KB Output is correct
80 Correct 966 ms 126736 KB Output is correct
81 Correct 948 ms 128272 KB Output is correct
82 Correct 1058 ms 126904 KB Output is correct
83 Correct 1138 ms 127344 KB Output is correct
84 Correct 1387 ms 87164 KB Output is correct
85 Correct 1336 ms 86956 KB Output is correct
86 Correct 1222 ms 85384 KB Output is correct
87 Correct 2062 ms 120400 KB Output is correct
88 Correct 1959 ms 119888 KB Output is correct
89 Correct 1971 ms 120388 KB Output is correct
90 Correct 2119 ms 121204 KB Output is correct
91 Correct 2023 ms 120652 KB Output is correct
92 Correct 2720 ms 124016 KB Output is correct
93 Correct 2679 ms 125284 KB Output is correct
94 Correct 2701 ms 122144 KB Output is correct
95 Correct 2776 ms 122600 KB Output is correct
96 Correct 3059 ms 122468 KB Output is correct
97 Correct 3123 ms 122088 KB Output is correct
98 Correct 2102 ms 123636 KB Output is correct
99 Correct 2151 ms 122384 KB Output is correct
100 Correct 2468 ms 123816 KB Output is correct
101 Correct 2248 ms 124404 KB Output is correct
102 Correct 2037 ms 120020 KB Output is correct
103 Correct 1854 ms 121700 KB Output is correct
104 Correct 1776 ms 121960 KB Output is correct
105 Correct 1197 ms 111316 KB Output is correct
106 Correct 1146 ms 110500 KB Output is correct
107 Correct 1273 ms 109352 KB Output is correct
108 Correct 1452 ms 110068 KB Output is correct