oj.uz

Submission #44735

# Submission time Handle Problem Language Result Execution time Memory
44735 2018-04-05T15:29:43 Z PowerOfNinjaGo Factories (JOI14_factories) C++11
15 / 100
 6000 ms 123552 KB 
//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];
int par[maxn];
ll sweep[maxn];
int cnt[maxn];
bool use[maxn];
ll bst[maxn];
void trv(int u, int p)
{
    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);
        }
    }
}
void dfs(int u, int p)
{
    cnt[u] = 1;
    for(auto edge : adj[u])
    {
        int v = edge.X;
        if(use[v] or v == p) continue;
        dfs(v, u);
        cnt[u] += cnt[v];
    }
}
int find_centroid(int u, int p, int full)
{
    for(auto edge : adj[u])
    {
        int v = edge.X;
        if(use[v] or v == p) continue;
        if(cnt[v]*2> full) return find_centroid(v, u, full);
    }
    return u;
}
void maketree(int top, int p)
{
    dfs(top, p);
    int c = find_centroid(top, p, cnt[top]);
    use[c] = true;
    par[c] = p;
    //printf("centroid %d\n", c);
    for(auto edge : adj[c])
    {
        int v = edge.X;
        if(use[v] or v == p) continue;
        maketree(v, c);
    }
}
int LCA(int u, int v)
{
    if(h[u]< h[v]) swap(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;
    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[])
{
    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<= N; i++) printf("sweep[i] = %lld\n", sweep[i]);
    maketree(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++) bst[i] = 4e18;
}
long long Query(int S, int X[], int T, int Y[])
{
    vector<int> vec;
    for(int i = 0; i< S; i++)
    {
        int u = X[i]+1;
        //printf("updating %d\n", u);
        while(u)
        {
            bst[u] = min(bst[u], dist(u, X[i]+1));
            //printf("bst[%d] is now %lld\n", u, bst[u]);
            vec.pb(u);
            u = par[u];
        }
    }
    ll best = 4e18;
    for(int i = 0; i< T; i++)
    {
        int u = Y[i]+1;
        int len = 0;
        while(u)
        {
            best = min(best, dist(u, Y[i]+1)+bst[u]);
            u = par[u];
            len++;
        }
    }
    for(auto x : vec) bst[x] = 4e18;
    return best;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 12664 KB Output is correct
2 Correct 2677 ms 21396 KB Output is correct
3 Correct 4810 ms 21416 KB Output is correct
4 Correct 4865 ms 21944 KB Output is correct
5 Correct 5897 ms 22012 KB Output is correct
6 Correct 1180 ms 22012 KB Output is correct
7 Correct 4977 ms 22012 KB Output is correct
8 Correct 5186 ms 22012 KB Output is correct
9 Correct 5767 ms 22012 KB Output is correct
10 Correct 1192 ms 31036 KB Output is correct
11 Correct 4760 ms 40612 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 40612 KB Output is correct
2 Execution timed out 6056 ms 116980 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6043 ms 123552 KB Time limit exceeded
2 Halted 0 ms 0 KB -