Submission #713536

#	Time	Username	Problem	Language	Result	Execution time	Memory
713536		Spade1	Factories (JOI14_factories)	C++14	Compilation error	0 ms	0 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
//#include "grader.cpp"
#define ll long long
#define int ll
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define pb push_back
#define INF INT_MAX
using namespace std;

const int maxN = 500050;

vector<pii> adj[maxN];
map<pll, ll> mp;
set<int> s;
bool mark[maxN];
ll sz[maxN], mn[maxN], up[maxN], root;

int dfs(int i, int prt=-1) {
    sz[i] = 1;
    for (auto [j, w] : adj[i]) {
        if (j == prt || mark[j]) continue;
        sz[i] += dfs(j, i);
    }
    return sz[i];
}

int find_centroid(int i, int m, int prt=-1) {
    for (auto [j, w] : adj[i]) {
        if (j == prt || mark[j]) continue;
        if (sz[j] > m/2) return find_centroid(j, m, i);
    }
    return i;
}

void dfs2(int i, ll dis=0, int prt=-1) {
    mp[{i, root}] = dis;
    mp[{root, i}] = dis;
    for (auto [j, w] : adj[i]) {
        if (j ==prt || mark[j]) continue;
        dfs2(j, dis+w, i);
    }
}

int decom(int x=0) {
    int cen = find_centroid(x, dfs(x));
    mark[cen] = 1;
    root = cen;
    dfs2(cen);

    for (auto [j, w] : adj[cen]) {
        if (mark[j]) continue;
        int c = decom(j);
        up[c] = cen;
    }
    return cen;
}

void update(int v) {
    int cur = v;
    while (cur != 0) {
        s.insert(cur);
        mn[cur] = min(mn[cur], mp[{cur, v}]);
        cur = up[cur];
    }
}

ll query(int v) {
    ll ans = LLONG_MAX, cur = v;
    while (cur != 0) {
        ans = min(ans, mn[cur] + mp[{cur, v}]);
        cur = up[cur];
    }
    return ans;
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N-1; ++i) {
        adj[A[i]].pb({B[i], D[i]});
        adj[B[i]].pb({A[i], D[i]});
    }
    for (int i = 0; i < N; ++i) mn[i] = INF;
    decom();
}

long long Query(int S, int X[], int T, int Y[]) {
    s.clear();
    for (int i = 0; i < S; ++i) update(X[i]);
    ll ans = LLONG_MAX;
    for (int i = 0; i < T; ++i) ans = min(ans, query(Y[i]));
    for (auto i : s) mn[i] = INF;
    return ans;
}

Compilation message (stderr)

factories.cpp: In function 'long long int dfs(long long int, long long int)':
factories.cpp:24:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |     for (auto [j, w] : adj[i]) {
      |               ^
factories.cpp: In function 'long long int find_centroid(long long int, long long int, long long int)':
factories.cpp:32:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |     for (auto [j, w] : adj[i]) {
      |               ^
factories.cpp: In function 'void dfs2(long long int, long long int, long long int)':
factories.cpp:42:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     for (auto [j, w] : adj[i]) {
      |               ^
factories.cpp: In function 'long long int decom(long long int)':
factories.cpp:54:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |     for (auto [j, w] : adj[cen]) {
      |               ^
/usr/bin/ld: /tmp/ccq8ncgw.o: in function `main':
grader.cpp:(.text.startup+0x37d): undefined reference to `Init(int, int*, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x412): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status