Submission #1160740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160740		phamducluong	Two Currencies (JOI23_currencies)	C++20	0 / 100	5095 ms	37068 KiB

currencies

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define F first
#define S second
#define all(p) p.begin(),p.end()
using namespace std;
const int mod = 20071008;
const int INF=1e18;
const int N = 1e5 + 5, M=1e6+5;
int n, m, q, c[N], l[N], r[N], s[N], t[N], x[N], y[N], a[N], cnt[N], par[N], h[N], Index[N], head[N], pos=1, id=1, res[N];
vector<int> e[N], qr[N];
pii ed[N];
void file()
{
    #define task "main"
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
void add(int &A, int B)
{
    A+=B;
    if(A>=mod) A-=mod;
}
void maximum(int &A, int B)
{
    if(A<B) A=B;
}
struct edge
{
    int u=0, v=0, w=0;
    bool operator< (const edge &a)
    {
        return w<a.w;
    }
} ev[N];
struct FenwickTree
{
    struct node
    {
        int val=0, cnt=0;
        node() {}
        node(int val, int cnt): val(val), cnt(cnt) {}
    };
    int n;
    vector<node> bit;
    void init(int _n)
    {
        n=_n;
        bit.resize(n+5);
    }
    void reset()
    {
        for(int i=1; i<=n; ++i) bit[i]={0,0};
    }
    node mer(node left, node right)
    {
        return node(left.val+right.val,left.cnt+right.cnt);
    }
    void update(int i, int val)
    {
        for(; i<=n; i+=i&-i) bit[i]=mer(bit[i],node(val,1));
    }
    node get(int i)
    {
        node res(0,0);
        for(; i>0; i-=i&-i) res=mer(res,bit[i]);
        return res;
    }
    node get(int l, int r)
    {
        node tmp1=get(r), tmp2=get(l-1);
        return node(tmp1.val-tmp2.val,tmp1.cnt-tmp2.cnt);
    }
} BIT;
void DFS(int u)
{
    cnt[u]=1;
    for(int v: e[u])
    {
        if(v==par[u]) continue;
        par[v]=u;
        DFS(v);
        cnt[u]+=cnt[v];
    }
}
void dfs(int u)
{
    for(int v: e[u])
    {
        if(v==par[u]) continue;
        h[v]+=h[u];
        dfs(v);
    }
}
void HLD(int u)
{
    if(head[id]==0) head[id]=u;
    Index[u]=id;
    a[u]=pos++;
    int nxt=0;
    for(int v: e[u]) if(v!=par[u] and cnt[v]>cnt[nxt]) nxt=v;
    if(nxt) HLD(nxt);
    for(int v: e[u])
    {
        if(v==par[u] or v==nxt) continue;
        ++id;
        HLD(v);
    }
}
int lca(int u, int v)
{
    while(Index[u]!=Index[v])
    {
        if(Index[u]>Index[v]) u=par[head[Index[u]]];
        else v=par[head[Index[v]]];
    }
    if(a[u]<a[v]) return u;
    return v;
}
int distance(int u, int v)
{
    int p=lca(u,v);
    return h[u]+h[v]-2*h[p];
}
FenwickTree::node query(int u, int v)
{
    int p=lca(u,v);
    FenwickTree::node res(0,0);
    while(Index[u]!=Index[p])
    {
        res=BIT.mer(res,BIT.get(a[head[Index[u]]],a[u]));
        u=par[head[Index[u]]];
    }
    while(Index[v]!=Index[p])
    {
        res=BIT.mer(res,BIT.get(a[head[Index[v]]],a[v]));
        v=par[head[Index[v]]];
    }
    if(a[u]<a[v]) res=BIT.mer(res,BIT.get(a[u],a[v]));
    else res=BIT.mer(res,BIT.get(a[v],a[u]));
    return res;
}
void Solve()
{
    cin>>n>>m>>q;
    for(int i=1; i<n; ++i)
    {
        cin>>ed[i].F>>ed[i].S;
        e[ed[i].F].push_back(ed[i].S);
        e[ed[i].S].push_back(ed[i].F);
    }
    BIT.init(n);
    DFS(1);
    HLD(1);
    for(int i=1; i<n; ++i) if(a[ed[i].F]<a[ed[i].S]) swap(ed[i].F,ed[i].S);
    for(int i=1; i<=m; ++i)
    {
        int p, c; cin>>p>>c;
        ev[i]={ed[p].F,ed[p].S,c};
        ++h[ed[p].F];
    }
    dfs(1);
    sort(ev+1,ev+m+1);
    for(int i=1; i<=q; ++i)
    {
        cin>>s[i]>>t[i]>>x[i]>>y[i];
        l[i]=1;
        r[i]=m;
    }
    while(1)
    {
        bool ok=false;
        for(int i=1; i<=q; ++i)
        {
            if(l[i]<=r[i])
            {
                ok=true;
                qr[(l[i]+r[i])>>1].push_back(i);
            }
        }
        if(!ok) break;
        for(int i=1; i<=m; ++i)
        {
            int u=ev[i].u, w=ev[i].w;
            BIT.update(a[u],w);
            for(int it: qr[i])
            {
                FenwickTree::node tmp=query(s[it],t[it]);
                if(tmp.val<=y[it]) l[it]=i+1;
                else r[it]=i-1;
            }
        }
        for(int i=1; i<n; ++i) qr[i].clear();
        BIT.reset();
    }
    for(int i=1; i<=q; ++i) qr[r[i]].push_back(i);
    for(int i=0; i<=m; ++i)
    {
        if(i>0)
        {
            int u=ev[i].u, w=ev[i].w;
            BIT.update(a[u],w);
        }
        for(int it: qr[i])
        {
            FenwickTree::node tmp=query(s[it],t[it]);
            int d=max(0ll,distance(s[it],t[it])-tmp.cnt);
            if(d<=x[it]) res[it]=x[it]-d;
            else res[it]=-1;
        }
    }
    for(int i=1; i<=q; ++i) cout<<res[i]<<"\n";
}

signed main()
{
    file();
    Solve();
    return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'void file()':
currencies.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 28
• Subtask 3: 0 / 30
• Subtask 4: 0 / 32