Submission #976596

#	Time	Username	Problem	Language	Result	Execution time	Memory
976596		saayan007	Factories (JOI14_factories)	C++17	0 / 100	46 ms	64236 KiB

factories

#include "factories.h"
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
#define rep(i, a, b) for(int (i) = (a); i <= (b); ++i)
#define repd(i, a, b) for(int (i) = (a); i >= (b); --i)

#define em emplace
#define eb emplace_back

#define fr first
#define sc second
#define mp make_pair

const char nl = '\n';

const int mxN = 5e5L + 10;
int n;

vector<pair<int, ll>> adj[mxN];
vector<pair<int, ll>> vir[mxN];
int color[mxN];

vector<int> cd[mxN];
int par[mxN];
int dep[mxN];
ll dist[mxN];
ll cX[mxN], cY[mxN];
const ll inf = 1e17L;

int tin[mxN], tout[mxN];
int tmr = 0;
int TEST = 0;
ll ans = 0;

#warning intand longlong are different

void dfs(int x, int p) {
    tin[x] = tmr++;
    for(auto U : adj[x]) {
        int y = U.fr; ll w = U.sc;
        if(y == p) continue;
        par[y] = x;
        dist[y] = w;
        dep[y] = dep[x] + 1;
        dfs(y, x);
    }
    tout[x] = tmr++;
    /* cout << "Node: "; cout << x << ' ' << par[x] << ' ' << dist[x] << ' ' << dep[x] << ' ' << tin[x] << ' ' << tout[x] << nl; */
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    /* cout << "Edges:\n"; */
    rep(i, 0, N - 2) {
        /* cout << A[i] << ' ' << B[i] << ' ' << D[i] << nl; */
        adj[A[i]].eb(B[i], ll(D[i]));
        adj[B[i]].eb(A[i], ll(D[i]));
    }
    /* cout << nl; */
    par[0] = -1;
    dist[0] = -1;
    dep[0] = 0;
    dfs(0, -1);
}

int lca(int u, int v) {
    if(dep[u] < dep[v]) swap(u, v);
    while(dep[u] > dep[v]) {
        u = par[u];
    }
    while(u != v) {
        u = par[u];
        v = par[v];
    }
    return u;
}

ll distance(int u, int v) {
    ll res = 0;
    if(dep[u] < dep[v]) swap(u, v);
    while(dep[u] > dep[v]) {
        res += dist[u];
        u = par[u];
    }
    while(u != v) {
        res += dist[u];
        u = par[u];
        res += dist[v];
        v = par[v];
    }
    return res;
}

void print(stack<int> x) {
    stack<int> y;
    while(!x.empty()) {
        y.push(x.top());
        x.pop();
    }
    while(!y.empty()) {
        cout << y.top() << ' ';
        x.push(y.top());
        y.pop();
    }
    cout << nl;
}

void sfd(int x, int p, ll dep) {
    if(color[x] == 1) ans = min(ans, dep);
    for(auto U : vir[x]) {
        int y = U.fr; ll w = U.sc;
        if(y == p) continue;
        sfd(y, x, dep + w);
    }
}

#warning make sure to reset global variablesj
long long Query(int S, int X[], int T, int Y[]) {
    /* cout << nl; */
    /* cout << "TESTCASE #" << ++TEST << endl; */
    // clearing virtual tree first
    rep(i, 0, S - 1) {
        color[X[i]] = 0;
        while(int(vir[X[i]].size())) vir[X[i]].pop_back();
    }
    rep(i, 0, T - 1) {
        color[Y[i]] = 1;
        while(int(vir[Y[i]].size())) vir[Y[i]].pop_back();
    }
    
    vector<int> nodes;
    rep(i, 0, S - 1) nodes.eb(X[i]);
    rep(i, 0, T - 1) nodes.eb(Y[i]);

    sort(nodes.begin(), nodes.end(), [&](int left, int right) {
        return tin[left] < tin[right];
    });
    /* cout << "Node order:"; */
    /* for(int x : nodes) { */
    /*     cout << x << ' '; */
    /* } */
    /* cout << nl; */

    /* cout << "Edges:\n"; */
    int nsz = S + T;
    while(nsz > 1) {
        int r = nsz - 1;
        int l = nsz - 2;
        if(tin[nodes[l]] < tin[nodes[r]] && tout[nodes[r]] < tout[nodes[l]]) {
            ll distlr = distance(nodes[r], nodes[l]);
            vir[nodes[r]].eb(nodes[l], distlr);
            vir[nodes[l]].eb(nodes[r], distlr);
            /* cout << nodes[l] << ' ' << nodes[r] << ' ' << distlr << nl; */
            nodes.pop_back(); --nsz;
            continue;
        }
        int anc = lca(nodes[r], nodes[l]);
        color[anc] = -1;
        while(int(vir[anc].size())) vir[anc].pop_back();

        ll distal = distance(nodes[l], anc);
        vir[anc].eb(nodes[l], distal);
        vir[nodes[l]].eb(anc, distal);
        /* cout << anc << ' ' << nodes[l] << ' ' << distal << nl; */
        nodes.pop_back(); --nsz;

        ll distar = distance(nodes[r], anc);
        vir[anc].eb(nodes[r], distar);
        vir[nodes[r]].eb(anc, distar);
        /* cout << anc << ' ' << nodes[r] << ' ' << distar << nl; */

        l -= 1;
        /* cout << "check:" << l << ' ' << nodes[l] << ' ' << anc << nl; */
        while(nsz > 0 && tin[anc] < tin[nodes[l]] && tout[nodes[l]] < tout[anc]) {
            /* cout << "check2:" << l << ' ' << nodes[l] << ' ' << anc << nl; */
            distal = distance(nodes[l], anc);
            vir[anc].eb(nodes[l], distal);
            vir[nodes[l]].eb(anc, distal);
            /* cout << anc << ' ' << nodes[l] << ' ' << distal << nl; */
            nodes.pop_back(); --nsz;
            --l;
            /* cout << "check:" << l << ' ' << nodes[l] << ' ' << anc << nl; */
        }
        /* cout << nl; */
    }

    ans = inf;
    rep(i, 0, S - 1) {
        sfd(X[i], -1, 0);
    }
    return ans;
#warning returning zero
    return 0;
}

Compilation message (stderr)

factories.cpp:37:2: warning: #warning intand longlong are different [-Wcpp]
   37 | #warning intand longlong are different
      |  ^~~~~~~
factories.cpp:119:2: warning: #warning make sure to reset global variablesj [-Wcpp]
  119 | #warning make sure to reset global variablesj
      |  ^~~~~~~
factories.cpp:194:2: warning: #warning returning zero [-Wcpp]
  194 | #warning returning zero
      |  ^~~~~~~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:6:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define rep(i, a, b) for(int (i) = (a); i <= (b); ++i)
      |                              ^
factories.cpp:56:5: note: in expansion of macro 'rep'
   56 |     rep(i, 0, N - 2) {
      |     ^~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:6:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define rep(i, a, b) for(int (i) = (a); i <= (b); ++i)
      |                              ^
factories.cpp:124:5: note: in expansion of macro 'rep'
  124 |     rep(i, 0, S - 1) {
      |     ^~~
factories.cpp:6:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define rep(i, a, b) for(int (i) = (a); i <= (b); ++i)
      |                              ^
factories.cpp:128:5: note: in expansion of macro 'rep'
  128 |     rep(i, 0, T - 1) {
      |     ^~~
factories.cpp:6:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define rep(i, a, b) for(int (i) = (a); i <= (b); ++i)
      |                              ^
factories.cpp:134:5: note: in expansion of macro 'rep'
  134 |     rep(i, 0, S - 1) nodes.eb(X[i]);
      |     ^~~
factories.cpp:6:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define rep(i, a, b) for(int (i) = (a); i <= (b); ++i)
      |                              ^
factories.cpp:135:5: note: in expansion of macro 'rep'
  135 |     rep(i, 0, T - 1) nodes.eb(Y[i]);
      |     ^~~
factories.cpp:6:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define rep(i, a, b) for(int (i) = (a); i <= (b); ++i)
      |                              ^
factories.cpp:190:5: note: in expansion of macro 'rep'
  190 |     rep(i, 0, S - 1) {
      |     ^~~

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