Submission #1303742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303742		Jakub_Wozniak	Designated Cities (JOI19_designated_cities)	C++20	100 / 100	619 ms	54968 KiB

designated_cities

#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
typedef long long ll;
typedef pair<ll,ll> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef pair<ld,ld> pld;
const ll mod = 1000000007;
const ll oo = (1e+18)+123;
const ll maxn = 2*(1e+5)+52;
const ll base = (1 << 19);
set<ll> S;
ll lsc[maxn];
ll licz = 0;
vector <pll> t[maxn];
ll dis[maxn][2];
ll dep[maxn] , ojc[maxn] , jump[maxn];
ll res[maxn];
set <pll> Q;
ll aktc[maxn];
ll sumall = 0;
ll sumzch = 0;

void DFS(ll v  , ll o , ll D)
{
    dep[v] = dep[o]+1;
    ojc[v] = o;
    if(dep[jump[o]] - dep[o] == dep[jump[jump[o]]]-dep[jump[o]])
    {
        jump[v] = jump[jump[o]];
    }
    else
    {
        jump[v] = o;
    }

    dis[v][0] = D;
    ll LIE = 0;
    for(auto p : t[v])
    {
        if(p.st == o)
        {
            LIE = p.nd;
            continue;
        }
        else
        {
            ;
        }
    }
    dis[v][1] = dis[o][1] + LIE;
    for(auto p : t[v])
    {
        if(p.st == o)
        {
            LIE = p.nd;
            sumzch += p.nd;
            continue;
        }
        else
        {
            DFS(p.st , v , D+p.nd);
        }
    }

    if(t[v].size() == 1)
    {
        licz++;
        lsc[licz] = v;
    }
}

ll LCA(ll a ,ll b)
{
    if(dep[a] > dep[b]) swap(b,a);
    while(dep[b] > dep[a])
    {
        if(dep[jump[b]] > dep[a]) b = jump[b];
        else b = ojc[b];
    }

    while(a!=b)
    {
        if(jump[a] == jump[b])
        {
            a = ojc[a] , b = ojc[b];
        }
        else
        {
            a = jump[a] , b = jump[b];
        }
    }

    return a;
}

void zap()
{
    ll q,F;
    cin >> q;
    while(q--)
    {
        cin >> F;
        cout << sumall-res[F] << '\n';
    }
}

ll l[maxn] , r[maxn];

void U(ll x)
{
    if(x <= 0 || x >= licz+1)return ;
    Q.erase({aktc[x] , x});
    ll L = l[x] , R = r[x];
    ll LL = 0, LR = 0;
    ll X = lsc[x];
    if(L != 0)LL = LCA(lsc[L],X);
    if(R != licz+1)LR = LCA(lsc[R],X);

    ll TEMP = 0;
    if(dep[LL] < dep[LR]) // LR
    {
        TEMP = dis[X][0]-dis[LR][0];
    }
    else // LL
    {
        TEMP = dis[X][0]-dis[LL][0];
    }

    ////cerr << "* " << TEMP << ' ' << LL << ' ' << LR << '\n';
    L = r[0] , R = l[licz+1];
    if(x == L)
    {
        auto it = S.begin();
        it++;
        ll J = lsc[*it];

        ll L1 = LCA(lsc[L],lsc[R]);
        ll L2 = LCA(J,lsc[R]);

        TEMP += dis[L2][1]-dis[L1][1];
    }
    else if(x == R)
    {
        auto it = S.end();
        it--;
        it--;
        ll J = lsc[*it];

        ll L1 = LCA(lsc[L],lsc[R]);
        ll L2 = LCA(lsc[L],J);
        ////cerr << "TIE: " << L1 << ' ' << L2 << '\n';
        //cerr << "TIE: " << dis[L2][1] << ' ' << dis[L1][1] << '\n';


        TEMP += dis[L2][1]-dis[L1][1];
    }

    aktc[x] = TEMP;
    Q.insert({aktc[x] , x});
    //cerr << x << ' ' << lsc[x] << ' ' << aktc[x] << '\n';
}



void wyn1(ll N)
{
    res[1] = 0;
    for(ll i = 1; i <= N ; i++)
    {
        res[1] = max(res[1] , sumzch - (dis[i][1]) + dis[i][0]);
    }
    return ;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll N , a , b , c , d;
    cin >> N;
    for(ll i =0 ; i < N-1 ; i++)
    {
        cin >> a >> b >> c >> d;
        t[a].push_back({b,c});
        t[b].push_back({a,d});
        sumall += c+d; 
    }

    ll rt = -1;
    for(ll i = 1; i <= N ; i++)
    {
        if(t[i].size() >= 2)
        {
            rt = i;
        }
    }

    if(rt == -1)
    {
        res[2] = sumall;
        res[1] = max(c,d);
        zap();
        exit(0);
    }


    DFS(rt , 0 , 0);

    for(ll i = 0 ; i <= licz ; i++)
    {
        r[i] = i+1;
    }
    for(ll i = 1;  i <=licz+1 ; i++)
    {
        l[i] = i-1;
    }

    for(ll i = licz ; i <= N ; i++) res[i] = sumall;
    for(ll i = 1; i <= licz;  i++)S.insert(i);
    for(ll i = 1; i <= licz;  i++)U(i);

    for(ll k = licz-1 ; k >= 1; k--)
    {
        auto p = Q.begin();
        auto P = *p;
        res[k] = res[k+1] - P.st;
        if(k == 1)break;
        Q.erase(p);
        S.erase(P.nd);
        ll L = l[P.nd] , R = r[P.nd];
        r[L] = R;
        l[R] = L;
        U(L);
        U(R);
        U(r[0]);
        U(l[licz+1]);
    }

    wyn1(N);

    zap();

    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44