oj.uz

Submission #778884

# Submission time Handle Problem Language Result Execution time Memory
778884 2023-07-11T00:42:46 Z onepunchac168 Two Currencies (JOI23_currencies) C++14
100 / 100
 1541 ms 90544 KB 
// created by Dinh Manh Hung
// onepunchac168
// THPT CHUYEN HA TINH
// HA TINH, VIET NAM
 
#include <bits/stdc++.h>
using namespace std;
 
//#pragma GCC optimize("O3,unroll-loops,no-stack-protector")
//#pragma GCC target("sse4,avx2,fma")
#define task ""
#define ldb long double
#define pb push_back
#define fi first
#define se second
#define pc pop_back()
#define all(x) begin(x),end(x)
#define uniquev(v) v.resize(unique(all(v))-v.begin())
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define cntbit(v) __builtin_popcountll(v)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) ((1LL*a*b)/__gcd(a,b))
#define mask(x) (1LL<<(x))
#define readbit(x,i) ((x>>i)&1)
#define ins insert
 
typedef long long ll;
typedef pair <ll,ll> ii;
typedef pair <ll,ii> iii;
typedef pair <ii,ii> iiii;
 
ll dx[]= {1,-1,0,0,1,-1,1,-1};
ll dy[]= {0,0,-1,1,1,-1,-1,1};
 
const ldb PI = acos (-1);
//const ll mod=978846151;
//const ll base=29;
const int maxn=1e6+5;
const int mod=1e9+7;
const char nl = '\n';
inline int ReadInt()
{
    char co;
    for (co = getchar(); co < '0' || co > '9'; co = getchar());
    int xo = co - '0';
    for (co = getchar(); co >= '0' && co <= '9'; co = getchar())
        xo = xo * 10 + co - '0';
    return xo;
}
 
void WriteInt(int xo)
{
    if (xo > 9)
        WriteInt(xo / 10);
    putchar(xo % 10 + '0');
}
/* END OF TEMPLATE*/
 
// ================= Solution =================//
const int N=1e5+5;
ll n,m,k;
vector <ll> vt[N];
ll p[N],c[N];
vector <ll> opt;
struct Node {
    int left,right;
    ll val;
    ll vala;
    Node(int left,int right,ll val,ll vala){
        this->left=left;
        this->right=right;
        this->val=val;
        this->vala=vala;
    }
    Node(){
 
    }
} T[N*24+5];
int ver[N];
vector <ll> tmp[N];
int Nnode=0;
int update(int oldnode,int l,int r,int u,ll val)
{
    if (l==r)
    {
        Nnode++;
        T[Nnode]=Node(0,0,val,val*opt[r-1]);
        return Nnode;
    }
    int mid=(l+r)/2;
    Nnode++;
    int newnode=Nnode;
    if (u<=mid)
    {
        T[newnode].left=update(T[oldnode].left,l,mid,u,val);
        T[newnode].right=T[oldnode].right;
        T[newnode].val=T[T[newnode].left].val+T[T[newnode].right].val;
        T[newnode].vala=T[T[newnode].left].vala+T[T[newnode].right].vala;
    }
    else
    {
        T[newnode].right=update(T[oldnode].right,mid+1,r,u,val);
        T[newnode].left=T[oldnode].left;
        T[newnode].val=T[T[newnode].left].val+T[T[newnode].right].val;
        T[newnode].vala=T[T[newnode].left].vala+T[T[newnode].right].vala;
    }
    return newnode;
 
}
ll query(int node,int l,int r,int u,int v)
{
    if (l>v||r<u)
    {
        return 0;
    }
    if (l>=u&&r<=v)
    {
        return T[node].val;
    }
    int mid=(l+r)/2;
    ll a1=query(T[node].left,l,mid,u,v);
    ll a2=query(T[node].right,mid+1,r,u,v);
    return a1+a2;
}
ll querya(int node,int l,int r,int u,int v)
{
    if (l>v||r<u)
    {
        return 0;
    }
    if (l>=u&&r<=v)
    {
        return T[node].vala;
    }
    int mid=(l+r)/2;
    ll a1=querya(T[node].left,l,mid,u,v);
    ll a2=querya(T[node].right,mid+1,r,u,v);
    return a1+a2;
}
map<ii,ll> mp;
ll cha[N][25];
ll sz[N];
void dfs(int u,int vv)
{
    for (auto v:vt[u])
    {
        if (v==vv)
        {
            continue;
        }
        cha[v][0]=u;
        sz[v]=sz[u]+1;
        for (int i=1;i<=20;i++)
        {
            cha[v][i]=cha[cha[v][i-1]][i-1];
        }
        dfs(v,u);
    }
}
void dfs1(int u,int vv)
{
    ver[u]=ver[vv];
    for (auto v:tmp[u])
    {
        ll aa=lower_bound(opt.begin(),opt.end(),v)-opt.begin()+1;
        ll bb=query(ver[u],1,opt.size(),aa,aa);
        ver[u]=update(ver[u],1,opt.size(),aa,bb+1);
    }
    for (auto v:vt[u])
    {
        if (v==vv)
        {
            continue;
        }
        dfs1(v,u);
    }
}
ll lca(int u,int v)
{
    if (sz[u]>sz[v]){swap(u,v);}
    for (int i=20;i>=0;i--)
    {
        if (sz[v]-mask(i)>=sz[u])
        {
            v=cha[v][i];
        }
    }
    if (u==v){return u;}
    for (int i=20;i>=0;i--)
    {
        if (cha[u][i]!=cha[v][i])
        {
            u=cha[u][i];
            v=cha[v][i];
        }
    }
    if (u!=v)
    {
        u=cha[u][0];
        v=cha[v][0];
    }
    return u;
}
ll ua[N],va[N];
void optmushnpr()
{
    cin>>n>>m>>k;
    T[0]=Node(0,0,0,0);
    ver[0]=0;
    for (int i=1;i<n;i++)
    {
        cin>>ua[i]>>va[i];
        vt[ua[i]].pb(va[i]);
        vt[va[i]].pb(ua[i]);
    }
    dfs(1,0);
    for (int i=1;i<=m;i++)
    {
        cin>>p[i]>>c[i];
        ll id=p[i];
        if (sz[ua[id]]>sz[va[id]])
        {
            tmp[ua[id]].pb(c[i]);
        }
        else
        {
            tmp[va[id]].pb(c[i]);
        }
        opt.pb(c[i]);
    }
    sort (opt.begin(),opt.end());
    uniquev(opt);
    dfs1(1,0);
    while (k--)
    {
        ll x,y,u,v;
        cin>>u>>v>>x>>y;
        ll left=1;ll right=opt.size();
        ll parent=lca(u,v);
        ll ans=opt.size();
        ll sum=querya(ver[u],1,opt.size(),1,opt.size())+querya(ver[v],1,opt.size(),1,opt.size())-2*querya(ver[parent],1,opt.size(),1,opt.size());
        while (left<=right)
        {
            ll mid=(left+right)/2;
            ll a1=querya(ver[u],1,opt.size(),1,mid);
            ll a2=querya(ver[v],1,opt.size(),1,mid);
            ll a3=querya(ver[parent],1,opt.size(),1,mid);
            if (a1+a2-2*a3>=y)
            {
                sum=a1+a2-2*a3;
                ans=mid;
                right=mid-1;
            }
            else left=mid+1;
        }
        ll ok=0;
        if (ans!=0)
        {
            if (sum>y)
            {
                ll h=(sum-y)/opt[ans-1];
                if (h*opt[ans-1]<sum-y)
                {
                    h++;
                }
                ok=h;
            }
        }
        ll a1=query(ver[u],1,opt.size(),ans+1,opt.size());
        ll a2=query(ver[v],1,opt.size(),ans+1,opt.size());
        ll a3=query(ver[parent],1,opt.size(),ans+1,opt.size());
        ok+=a1+a2-2*a3;
        if (ok<=x)
        {
            cout<<x-ok<<nl;
        }
        else cout<<-1<<nl;
    }
}
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen(task".inp","r")){
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);}
    int t;
    t=1;
    //cin>>t;
    while (t--){optmushnpr();}
}
 
// goodbye see ya

Compilation message

currencies.cpp: In function 'int main()':
currencies.cpp:286:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  286 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:287:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  287 |     freopen(task".out","w",stdout);}
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 5076 KB Output is correct
5 Correct 7 ms 6228 KB Output is correct
6 Correct 8 ms 6208 KB Output is correct
7 Correct 7 ms 5940 KB Output is correct
8 Correct 9 ms 6220 KB Output is correct
9 Correct 9 ms 6228 KB Output is correct
10 Correct 9 ms 6332 KB Output is correct
11 Correct 9 ms 6336 KB Output is correct
12 Correct 9 ms 6228 KB Output is correct
13 Correct 10 ms 6356 KB Output is correct
14 Correct 10 ms 6356 KB Output is correct
15 Correct 10 ms 6360 KB Output is correct
16 Correct 11 ms 6336 KB Output is correct
17 Correct 15 ms 6360 KB Output is correct
18 Correct 10 ms 6360 KB Output is correct
19 Correct 9 ms 6332 KB Output is correct
20 Correct 8 ms 6332 KB Output is correct
21 Correct 9 ms 6336 KB Output is correct
22 Correct 9 ms 6228 KB Output is correct
23 Correct 9 ms 6228 KB Output is correct
24 Correct 12 ms 6228 KB Output is correct
25 Correct 9 ms 6228 KB Output is correct
26 Correct 8 ms 6340 KB Output is correct
27 Correct 8 ms 6336 KB Output is correct
28 Correct 9 ms 6228 KB Output is correct
29 Correct 8 ms 6240 KB Output is correct
30 Correct 5 ms 5716 KB Output is correct
31 Correct 5 ms 5716 KB Output is correct
32 Correct 9 ms 5716 KB Output is correct
33 Correct 10 ms 6468 KB Output is correct
34 Correct 11 ms 6612 KB Output is correct
35 Correct 9 ms 6484 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 5 ms 5716 KB Output is correct
3 Correct 5 ms 5816 KB Output is correct
4 Correct 5 ms 5716 KB Output is correct
5 Correct 147 ms 41872 KB Output is correct
6 Correct 148 ms 33088 KB Output is correct
7 Correct 152 ms 35908 KB Output is correct
8 Correct 132 ms 36060 KB Output is correct
9 Correct 134 ms 36264 KB Output is correct
10 Correct 178 ms 43280 KB Output is correct
11 Correct 182 ms 43444 KB Output is correct
12 Correct 183 ms 43328 KB Output is correct
13 Correct 191 ms 43264 KB Output is correct
14 Correct 176 ms 43284 KB Output is correct
15 Correct 253 ms 50660 KB Output is correct
16 Correct 256 ms 51184 KB Output is correct
17 Correct 248 ms 50320 KB Output is correct
18 Correct 219 ms 43320 KB Output is correct
19 Correct 254 ms 43220 KB Output is correct
20 Correct 214 ms 43336 KB Output is correct
21 Correct 162 ms 42716 KB Output is correct
22 Correct 154 ms 42992 KB Output is correct
23 Correct 148 ms 42952 KB Output is correct
24 Correct 160 ms 42924 KB Output is correct
25 Correct 171 ms 43192 KB Output is correct
26 Correct 165 ms 43172 KB Output is correct
27 Correct 176 ms 43188 KB Output is correct
28 Correct 144 ms 43060 KB Output is correct
29 Correct 149 ms 43172 KB Output is correct
30 Correct 155 ms 43320 KB Output is correct
31 Correct 152 ms 43364 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5044 KB Output is correct
2 Correct 12 ms 6468 KB Output is correct
3 Correct 10 ms 6484 KB Output is correct
4 Correct 10 ms 6496 KB Output is correct
5 Correct 646 ms 70420 KB Output is correct
6 Correct 592 ms 63016 KB Output is correct
7 Correct 973 ms 70748 KB Output is correct
8 Correct 1416 ms 90544 KB Output is correct
9 Correct 1362 ms 90444 KB Output is correct
10 Correct 1386 ms 90484 KB Output is correct
11 Correct 1091 ms 89992 KB Output is correct
12 Correct 1193 ms 90216 KB Output is correct
13 Correct 1089 ms 89960 KB Output is correct
14 Correct 690 ms 90460 KB Output is correct
15 Correct 757 ms 90460 KB Output is correct
16 Correct 880 ms 90456 KB Output is correct
17 Correct 857 ms 90464 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 5076 KB Output is correct
5 Correct 7 ms 6228 KB Output is correct
6 Correct 8 ms 6208 KB Output is correct
7 Correct 7 ms 5940 KB Output is correct
8 Correct 9 ms 6220 KB Output is correct
9 Correct 9 ms 6228 KB Output is correct
10 Correct 9 ms 6332 KB Output is correct
11 Correct 9 ms 6336 KB Output is correct
12 Correct 9 ms 6228 KB Output is correct
13 Correct 10 ms 6356 KB Output is correct
14 Correct 10 ms 6356 KB Output is correct
15 Correct 10 ms 6360 KB Output is correct
16 Correct 11 ms 6336 KB Output is correct
17 Correct 15 ms 6360 KB Output is correct
18 Correct 10 ms 6360 KB Output is correct
19 Correct 9 ms 6332 KB Output is correct
20 Correct 8 ms 6332 KB Output is correct
21 Correct 9 ms 6336 KB Output is correct
22 Correct 9 ms 6228 KB Output is correct
23 Correct 9 ms 6228 KB Output is correct
24 Correct 12 ms 6228 KB Output is correct
25 Correct 9 ms 6228 KB Output is correct
26 Correct 8 ms 6340 KB Output is correct
27 Correct 8 ms 6336 KB Output is correct
28 Correct 9 ms 6228 KB Output is correct
29 Correct 8 ms 6240 KB Output is correct
30 Correct 5 ms 5716 KB Output is correct
31 Correct 5 ms 5716 KB Output is correct
32 Correct 9 ms 5716 KB Output is correct
33 Correct 10 ms 6468 KB Output is correct
34 Correct 11 ms 6612 KB Output is correct
35 Correct 9 ms 6484 KB Output is correct
36 Correct 3 ms 4948 KB Output is correct
37 Correct 5 ms 5716 KB Output is correct
38 Correct 5 ms 5816 KB Output is correct
39 Correct 5 ms 5716 KB Output is correct
40 Correct 147 ms 41872 KB Output is correct
41 Correct 148 ms 33088 KB Output is correct
42 Correct 152 ms 35908 KB Output is correct
43 Correct 132 ms 36060 KB Output is correct
44 Correct 134 ms 36264 KB Output is correct
45 Correct 178 ms 43280 KB Output is correct
46 Correct 182 ms 43444 KB Output is correct
47 Correct 183 ms 43328 KB Output is correct
48 Correct 191 ms 43264 KB Output is correct
49 Correct 176 ms 43284 KB Output is correct
50 Correct 253 ms 50660 KB Output is correct
51 Correct 256 ms 51184 KB Output is correct
52 Correct 248 ms 50320 KB Output is correct
53 Correct 219 ms 43320 KB Output is correct
54 Correct 254 ms 43220 KB Output is correct
55 Correct 214 ms 43336 KB Output is correct
56 Correct 162 ms 42716 KB Output is correct
57 Correct 154 ms 42992 KB Output is correct
58 Correct 148 ms 42952 KB Output is correct
59 Correct 160 ms 42924 KB Output is correct
60 Correct 171 ms 43192 KB Output is correct
61 Correct 165 ms 43172 KB Output is correct
62 Correct 176 ms 43188 KB Output is correct
63 Correct 144 ms 43060 KB Output is correct
64 Correct 149 ms 43172 KB Output is correct
65 Correct 155 ms 43320 KB Output is correct
66 Correct 152 ms 43364 KB Output is correct
67 Correct 2 ms 5044 KB Output is correct
68 Correct 12 ms 6468 KB Output is correct
69 Correct 10 ms 6484 KB Output is correct
70 Correct 10 ms 6496 KB Output is correct
71 Correct 646 ms 70420 KB Output is correct
72 Correct 592 ms 63016 KB Output is correct
73 Correct 973 ms 70748 KB Output is correct
74 Correct 1416 ms 90544 KB Output is correct
75 Correct 1362 ms 90444 KB Output is correct
76 Correct 1386 ms 90484 KB Output is correct
77 Correct 1091 ms 89992 KB Output is correct
78 Correct 1193 ms 90216 KB Output is correct
79 Correct 1089 ms 89960 KB Output is correct
80 Correct 690 ms 90460 KB Output is correct
81 Correct 757 ms 90460 KB Output is correct
82 Correct 880 ms 90456 KB Output is correct
83 Correct 857 ms 90464 KB Output is correct
84 Correct 438 ms 73848 KB Output is correct
85 Correct 535 ms 61740 KB Output is correct
86 Correct 504 ms 48676 KB Output is correct
87 Correct 793 ms 82368 KB Output is correct
88 Correct 784 ms 82436 KB Output is correct
89 Correct 811 ms 82416 KB Output is correct
90 Correct 812 ms 82464 KB Output is correct
91 Correct 830 ms 82368 KB Output is correct
92 Correct 1541 ms 87536 KB Output is correct
93 Correct 1473 ms 89344 KB Output is correct
94 Correct 1049 ms 82460 KB Output is correct
95 Correct 1052 ms 82492 KB Output is correct
96 Correct 1049 ms 82472 KB Output is correct
97 Correct 1067 ms 82476 KB Output is correct
98 Correct 690 ms 82108 KB Output is correct
99 Correct 691 ms 82132 KB Output is correct
100 Correct 692 ms 82140 KB Output is correct
101 Correct 674 ms 82272 KB Output is correct
102 Correct 816 ms 82368 KB Output is correct
103 Correct 862 ms 82340 KB Output is correct
104 Correct 793 ms 82336 KB Output is correct
105 Correct 660 ms 82664 KB Output is correct
106 Correct 655 ms 82492 KB Output is correct
107 Correct 642 ms 82528 KB Output is correct
108 Correct 632 ms 82396 KB Output is correct