Submission #44749

#	Time	Username	Problem	Language	Result	Execution time	Memory
44749		PowerOfNinjaGo	Factories (JOI14_factories)	C++17	15 / 100	6031 ms	114284 KiB

factories

//Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
    #include "grader.cpp"
#else
    #include "factories.h"
#endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector< ii > vii;
#define X first
#define Y second
#define pb push_back
const int maxn = 5e5+5;
vii adj[maxn];
int dp[22][maxn];
int h[maxn];
ll sweep[maxn];
int cnt[maxn];
bool use[maxn];
int tim = 1;
int zil[maxn];
ll red[4*maxn], blue[4*maxn];
int n;
ll query(ll *st, int i, int j, int p = 1, int L = 1, int R = n)
{
    if(i> R || j< L) return 4e18;
    if(i<= L && R<= j) return st[p];
    ll x = query(st, i, j, 2*p, L, (L+R)/2);
    ll y = query(st, i, j, 2*p+1, (L+R)/2+1, R);
    return min(x, y);
}
void update(ll *st, int id, ll dx, int p = 1, int L = 1, int R = n)
{
    if(L == R)
    {
        st[p] = dx;
        return;
    }
    int M = (L+R)/2;
    if(id<= M) update(st, id, dx, 2*p, L, M);
    else update(st, id, dx, 2*p+1, M+1, R);
    st[p] = min(st[2*p], st[2*p+1]);
}
void trv(int u, int p)
{
    cnt[u] = 1;
    zil[u] = tim;
    tim++;
    for(auto edge : adj[u])
    {
        int v = edge.X, w = edge.Y;
        if(v != p)
        {
            h[v] = h[u]+1;
            dp[0][v] = u;
            sweep[v] = sweep[u]+w;
            trv(v, u);
            cnt[u] += cnt[v];
        }
    }
}
bool cmp(int u, int v)
{
    return zil[u]< zil[v];
}
int LCA(int u, int v)
{
    if(h[u]< h[v]) swap(u, v);
    //printf("%d %d\n", u, v);
    for(int i = 20; i>= 0; i--)
    {
        int x = dp[i][u];
        if(h[x]>= h[v]) u = x;
    }
    if(u == v) return u;
    //printf("%d\n", h[7]);
    //printf("now %d %d\n", u, v);
    for(int i = 20; i>= 0; i--)
    {
        int x = dp[i][u], y = dp[i][v];
        if(x == y) continue;
        u = x; v = y;
    }
    return dp[0][u];
}
ll dist(int u, int v)
{
    int x = LCA(u, v);
    return sweep[u]+sweep[v]-2LL*sweep[x];
}
void Init(int N, int A[], int B[], int D[])
{
    n = N;
    for(int i = 0; i< N-1; i++)
    {
        int u, v; u = A[i]+1; v = B[i]+1;
        int w = D[i];
        adj[u].pb(ii(v, w));
        adj[v].pb(ii(u, w));
    }
    h[1] = 1; trv(1, 0);
    for(int i = 1; i<= 20; i++)
        for(int j = 1; j<= N; j++)
            dp[i][j] = dp[i-1][dp[i-1][j]];
    for(int i = 1; i<= N; i++)
    {
        update(red, i, 4e18);
        update(blue, i, 4e18);
    }
}
long long Query(int S, int X[], int T, int Y[])
{
    vector<int> all;
    for(int i = 0; i< S; i++) all.pb(X[i]+1);
    for(int i = 0; i< T; i++) all.pb(Y[i]+1);
    sort(all.begin(), all.end(), cmp);
    //for(auto x : all) printf("%d ", x);
    //printf("\n");
    vector<int> matt; matt = all;
    for(int i = 1; i< (int) all.size(); i++)
    {
        matt.pb(LCA(all[i], all[i-1]));
    }
    for(int i = 0; i< S; i++) update(red, zil[X[i]+1], sweep[X[i]+1]);
    for(int i = 0; i< T; i++) update(blue, zil[Y[i]+1], sweep[Y[i]+1]);
    sort(matt.begin(), matt.end());
    matt.resize(unique(matt.begin(), matt.end())-matt.begin());
    //for(auto top : matt) printf("%d ", top);
    //printf("\n");
    ll best = 4e18;
    for(auto top : matt)
    {
        ll bestred = query(red, zil[top], zil[top]+cnt[top]-1);
        ll bestblue = query(blue, zil[top], zil[top]+cnt[top]-1);
        best = min(best, bestred+bestblue-2*sweep[top]);
    }
    for(int i = 0; i< S; i++) update(red, zil[X[i]+1], 4e18);
    for(int i = 0; i< T; i++) update(blue, zil[Y[i]+1], 4e18);
    return best;
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67