Submission #1262275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262275		Szymon_Pilipczuk	Two Currencies (JOI23_currencies)	C++20	0 / 100	21 ms	3396 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(),a.end()
#define rep(a,b) for(int a = 0;a<b;a++)
const int inf = 1e9;
const ll infl = 1e18;
int d[100000];
int cpr = 0;
int pr[100000];
int rpr[100000];
int mpr[100000];
bool vis[100000];
int jp[100000][20];
vector<int> gr[100000]; 
void dfs(int v,int cd)
{
    d[v] = cd;
    vis[v] = true;
    rpr[cpr] = v;
    pr[v] = cpr;
    cpr++;
    for(int i : gr[v])
    {
        if(!vis[i])
        {
            jp[i][0] = v;
            dfs(i,cd+1);
        }
    }
    mpr[v] = cpr;
}
int lca(int a,int b)
{
    if(d[a] < d[b]) swap(a,b);
    for(int i = 19;i>=0;i--)
    {
        if(d[a] - (1<<i) >= d[b])
        {
            a = jp[a][i];
        }
    }
    for(int i = 19;i>=0;i--)
    {
        if(jp[a][i] != jp[b][i])
        {
            a = jp[a][i];
            b = jp[b][i];
        }
    }
    if(a==b)return a;
    return jp[a][0];
}
int n,m,q;
pair<int,int> tr[200000];
void add(int l,int r,int v,int v2)
{
    //cerr<<l<<" "<<r<<" "<<v2<<" CAMERAMAN"<<"\n";
    l+=n;r+=n;
    tr[l].st += v;
    tr[l].nd += v2;
    if(l != r)
    {
        tr[r].st += v;
        tr[r].nd += v2;
    }
    while(l/2 != r/2)
    {
        if(l%2==0)
        {
            tr[l+1].st+=v;
            tr[l+1].nd+=v2;
        }
        if(r%2==1)
        {
            tr[r-1].st+=v;
            tr[r-1].nd+=v2;
        }
        l/=2;r/=2;
    }
}
pair<ll,int> check(int p)
{
    p = pr[p];
    p += n;
    pair<ll,int> ans = {0,0};
    while(p > 0)
    {
        
        ans.st += tr[p].st;
        ans.nd += tr[p].nd;
        p/=2;
    }
    return ans;
}
void add2(int p,int c)
{
    add(pr[p],mpr[p]-1,c,-1);
}
vector<pair<int,int>> ch;
void my_clear()
{
    rep(i,n*2)
    {
        tr[i] = {0,0};
    }
    rep(i,m)
    {
        //cerr<<ch[i].st<<" "<<ch[i].nd<<" "<<rpr[ch[i].nd]<<" "<<mpr[rpr[ch[i].nd]]<<" aaa\n";
        add(ch[i].nd,mpr[rpr[ch[i].nd]]-1,0,1);
    }
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); 
    //cerr.tie(0);
    cin>>n>>m>>q;
    ch.resize(m);
    vector<pair<int,int>> kr(n-1);
    rep(i,n-1)
    {
        int a,b;
        cin>>a>>b;
        a--;b--;
        gr[a].pb(b);
        gr[b].pb(a);
        kr[i] = {a,b};
    }
    dfs(0,0);
    jp[0][0] = 0;
    for(int i = 1;i<20;i++)
    {
        rep(j,n)
        {
            jp[j][i] = jp[jp[j][i-1]][i-1];
        }
    }
    rep(i,m)
    {
        int p,c;
        cin>>p>>c;
        p--;
        ch[i] = {c,max(pr[kr[p].st],pr[kr[p].nd])};
        ////cerr<<ch[i].nd<<"\n";
    }
   // //cerr<<"\n";
   // return 0;
    sort(all(ch));
    vector<array<ll,6>> que(q);
    vector<pair<ll,int>> cans(q);
    rep(i,q)
    {
        cin>>que[i][0]>>que[i][1]>>que[i][2]>>que[i][3];
        que[i][0]--;que[i][1]--;
        que[i][4] = 0;
        que[i][5] = inf+1;
    }
    vector<pair<ll,int>> rbs(q);
    for(int i = 0;i<31;i++)
    {
        
        //cerr<<"\n";
        my_clear();
        rbs.clear();
        rbs.resize(q);
        rep(j,q)
        {
            rbs[j] = {(que[j][4]+que[j][5])/2,j};
        }
        sort(all(rbs));
        int r = 0;
        rep(j,q)
        {
            while(r < m && ch[r].st <= rbs[j].st)
            {
                add2(rpr[ch[r].nd],ch[r].st);
                //cerr<<ch[r].st<<" "<<ch[r].nd<<" "<<rpr[ch[r].nd]<<" TOILET\n";
                r++;
            }
            int cu = rbs[j].nd;
            if(que[cu][4] + 1 >= que[cu][5]) continue;
            pair<ll,int> cc;
            cc.st = check(que[cu][0]).st + check(que[cu][1]).st - check(lca(que[cu][0],que[cu][1])).st * 2;
            //cerr<< check(que[cu][0]).nd<<" "<<check(que[cu][1]).nd<<" "<<check(lca(que[cu][0],que[cu][1])).nd<<" "<<que[cu][1]<<" SKIBIDI\n";
            cc.nd = check(que[cu][0]).nd + check(que[cu][1]).nd - check(lca(que[cu][0],que[cu][1])).nd * 2;
            //cerr<<j<<" "<<rbs[j].st<<" "<<rbs[j].nd<<"\n";
            if(cc.st >= que[cu][3])
            {
                //cerr<<rbs[j].st<<" "<<rbs[j].nd<<"\n";
                cans[cu] = {cc.st,cc.nd};
                que[cu][5] = rbs[j].st;
            }
            else
            {
                que[cu][4] = rbs[j].st;
            }
        }
    }
    vector<int> tans(q);
    rep(i,q)
    {
        //cerr<<cans[i].nd<<" "<<que[i][5]<<" "<<cans[i].st<<" "<<que[i][3]<<"\n";
        tans[i] = que[i][2]-cans[i].nd - (que[i][5] - 1 + cans[i].st - que[i][3])/que[i][5];
        if(tans[i] < 0)
        {
            cout<<-1<<"\n";
        }
        else
        {
            cout<<tans[i]<<"\n";
        }
    }


}

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