Submission #71956

#	Time	Username	Problem	Language	Result	Execution time	Memory
71956		anishmahto	Factories (JOI14_factories)	C++14	100 / 100	7217 ms	412144 KiB

factories

#include <iostream>
#include <cstdio>
#include <string.h>
#include <vector>
#include <limits>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <deque>
#define SET(x,y) x |= (1 << y)
#define CLEAR(x,y) x &= ~(1<< y)
#define READ(x,y) ((0u == (x & (1<<y)))?0u:1u)
#define TOGGLE(x,y) (x ^= (1<<y))
#define watch(x) cout << (#x) << " is " << (x) << endl
#define pb push_back
#define mp make_pair
#define si(n) scanf("%d",&n)
#define sf(n) scanf("%f",&n)
#define sl(n) scanf("%lld",&n)
#define slu(n) scanf("%llu",&n)
#define sd(n) scanf("%lf",&n)
#define ss(n) scanf("%s",n)
#define pnl printf("\n")
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORR(i,n) for(int i=(n);i>=0;i--)
#define CL(a,b) memset(a,b,sizeof(a))
#define sqr(x) ((x)*(x))
#define intLIMIT numeric_limits<int>
#define longLIMIT numeric_limits<long long>
#define dbl(x) (double)(x)
#define vi vector <int>
#define vii vector < pair <int, int> > 
#define vll vector <long long>
#define fastCin cin.sync_with_stdio(0);cin.tie(0)
#define scanUnsigned(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
using namespace std;
void PRINT (int x, int y) { for (int i = y-1; i >= 0; i--) { cout << READ(x,i); } cout << endl; }

vector < vector < pll > > graph(500001);
const int LG = (int)log2(500001)+2;
long long sz[500001] = {0}, depth[500001], cTreeDist[500001][LG], dp[500001], path[500001][LG];
bool v[500001] = {0};

ll getSz (int pos, int par) {
    sz[pos] = 1;
    REP (x, graph[pos].size()) {
        if (v[graph[pos][x].first] || graph[pos][x].first == par) {
            continue;
        }
        sz[pos] += getSz(graph[pos][x].first, pos);
    }
    return sz[pos];
}

ll findCentroid (int pos, int par, int tot) {
    REP (x, graph[pos].size()) {
        if (v[graph[pos][x].first] || graph[pos][x].first == par) {
            continue;
        }
        if (sz[graph[pos][x].first] > tot/2) {
            return findCentroid (graph[pos][x].first, pos, tot);
        }
    }
    return pos;
}

void buildDist (int pos, int par, ll c, ll lvl, int centroid) {
    cTreeDist[pos][lvl] = c;
    path[pos][lvl] = centroid;
    depth[pos] = lvl;
    REP (x, graph[pos].size()) {
        if (v[graph[pos][x].first] || graph[pos][x].first == par) {
            continue;
        }
        buildDist (graph[pos][x].first, pos, c + graph[pos][x].second, lvl, centroid);
    }
}

void build (int pos, int par, int lvl) {
    int tot = getSz (pos, -1);
    int centroid = findCentroid (pos, -1, tot);
    v[centroid] = true;
    buildDist (centroid, -1, (ll)0, lvl, centroid);
    REP (x, graph[centroid].size()) {
        if (v[graph[centroid][x].first]) {
            continue;
        }
        build(graph[centroid][x].first, centroid, lvl+1);
    }
}

void Init(int N, int A[], int B[], int D[]) {
    CL (dp, -1);
    REP (x, N-1) {
        graph[A[x]].pb(mp(B[x], D[x]));
        graph[B[x]].pb(mp(A[x], D[x]));
    }
    build (0, -1, 0);
}

long long Query(int S, int X[], int T, int Y[]) {
    ll ans = longLIMIT::max();
    vi idx;
    REP (x, S) {
        dp[X[x]] = 0;
        idx.pb (X[x]);
        int pos = depth[X[x]];
        while (pos >= 0) {
            if (dp[path[X[x]][pos]] == -1) {
                dp[path[X[x]][pos]] = cTreeDist[X[x]][pos];
                idx.pb (path[X[x]][pos]);
            } else {
                dp[path[X[x]][pos]] = min (dp[path[X[x]][pos]], cTreeDist[X[x]][pos]);
            }
            pos--;
        }
    }
    REP (x, T) {
        if (dp[Y[x]] != -1) {
            ans = min (ans, dp[Y[x]]);
        }
        int pos = depth[Y[x]];
        while (pos >= 0) {
            if (dp[path[Y[x]][pos]] != -1) {
                ans = min (ans, cTreeDist[Y[x]][pos] + dp[path[Y[x]][pos]]);
            }
            pos--;
        }
    }
    while (!idx.empty()) {
        dp[idx.back()] = -1;
        idx.pop_back();
    }
    return ans;
}

Compilation message (stderr)

factories.cpp: In function 'long long int getSz(int, int)':
factories.cpp:27:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,n) for(int i=0;i<(n);i++)
                               ^
factories.cpp:51:5: note: in expansion of macro 'REP'
     REP (x, graph[pos].size()) {
     ^~~
factories.cpp: In function 'long long int findCentroid(int, int, int)':
factories.cpp:27:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,n) for(int i=0;i<(n);i++)
                               ^
factories.cpp:61:5: note: in expansion of macro 'REP'
     REP (x, graph[pos].size()) {
     ^~~
factories.cpp: In function 'void buildDist(int, int, long long int, long long int, int)':
factories.cpp:27:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,n) for(int i=0;i<(n);i++)
                               ^
factories.cpp:76:5: note: in expansion of macro 'REP'
     REP (x, graph[pos].size()) {
     ^~~
factories.cpp: In function 'void build(int, int, int)':
factories.cpp:27:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,n) for(int i=0;i<(n);i++)
                               ^
factories.cpp:89:5: note: in expansion of macro 'REP'
     REP (x, graph[centroid].size()) {
     ^~~

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