oj.uz

Submission #393188

# Submission time Handle Problem Language Result Execution time Memory
393188 2021-04-22T23:00:50 Z jeroenodb Factories (JOI14_factories) C++14
100 / 100
 4172 ms 249372 KB 
#include "factories.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 5e5+1;
const ll oo = 1e18;
vector<pair<int,ll>> adj[mxN];
int sz[mxN];
bitset<mxN> visited;
struct anc {
    int i;
    ll d;
};
anc ancs[mxN][20];
int ancsz[mxN];
int curcentroid;
void dfsz(int at,int from=-1) {
    sz[at]=1;
    for(auto [to,w]: adj[at]) if(to!=from and !visited[to]) {
        dfsz(to,at);
        sz[at]+=sz[to];
    }
}
void dfsd(int at,int from=-1,ll d=0) {
    ancs[at][ancsz[at]++] = {curcentroid,d};
    for(auto [to,w]: adj[at]) if(to!=from and !visited[to]) {
        dfsd(to,at,w+d);
    }
}
int centroid(int at) {
    int from=-1,total=sz[at];
    bool done = false;
    while(!done) {
        done = true;
        for(auto [to,w]: adj[at]) if(to!=from and !visited[to]) {
            if(sz[to]*2>total) {
                from = at;
                at = to;
                done = false;
                break;
            }
        }
    }
    return at;
}
void decomp(int at) {
    dfsz(at);
    int c = curcentroid = centroid(at);
    dfsd(c);

    visited[c] = true;
    for(auto [to,w]: adj[c]) if(!visited[to]) {
        decomp(to);
    }
    visited[c]= false;
}
ll mn[mxN];
void Init(int N, int A[], int B[], int D[]) {
    for(int i=0;i<N;++i) {
        adj[i].clear();
        ancsz[i]=0;
    }
    for(int i=0;i<N-1;++i) {
        adj[A[i]].push_back({B[i],D[i]});
        adj[B[i]].push_back({A[i],D[i]});
    }
    decomp(0);
    fill(mn,mn+N,oo);
}


int st[mxN],p;
long long Query(int S, int X[], int T, int Y[]) {
    p=0;
    for(int i=0;i<S;++i) {
        int x = X[i];
        for(int j=0;j<ancsz[x];++j) {
            auto& a = ancs[x][j];
            if(mn[a.i]==oo) {
                st[p++]=a.i;  
            }
            mn[a.i] = min(mn[a.i],a.d);
        }
    }
    ll ans = oo;
    for(int i=0;i<T;++i) {
        int y = Y[i];
        for(int j=0;j<ancsz[y];++j) {
            auto& a = ancs[y][j];
            ans = min(ans, mn[a.i]+a.d);
        }
    }
    for(int i=0;i<p;++i) {
        mn[st[i]] = oo;
    }
    return ans;
}

Compilation message

factories.cpp: In function 'void dfsz(int, int)':
factories.cpp:23:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |     for(auto [to,w]: adj[at]) if(to!=from and !visited[to]) {
      |              ^
factories.cpp: In function 'void dfsd(int, int, ll)':
factories.cpp:30:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |     for(auto [to,w]: adj[at]) if(to!=from and !visited[to]) {
      |              ^
factories.cpp: In function 'int centroid(int)':
factories.cpp:39:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |         for(auto [to,w]: adj[at]) if(to!=from and !visited[to]) {
      |                  ^
factories.cpp: In function 'void decomp(int)':
factories.cpp:56:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |     for(auto [to,w]: adj[c]) if(!visited[to]) {
      |              ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12492 KB Output is correct
2 Correct 350 ms 21980 KB Output is correct
3 Correct 362 ms 22236 KB Output is correct
4 Correct 344 ms 22048 KB Output is correct
5 Correct 367 ms 22436 KB Output is correct
6 Correct 279 ms 22008 KB Output is correct
7 Correct 359 ms 22100 KB Output is correct
8 Correct 355 ms 22084 KB Output is correct
9 Correct 360 ms 22468 KB Output is correct
10 Correct 312 ms 22024 KB Output is correct
11 Correct 357 ms 22084 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12492 KB Output is correct
2 Correct 2084 ms 215084 KB Output is correct
3 Correct 3111 ms 218780 KB Output is correct
4 Correct 929 ms 212628 KB Output is correct
5 Correct 3795 ms 249372 KB Output is correct
6 Correct 3067 ms 220076 KB Output is correct
7 Correct 947 ms 61572 KB Output is correct
8 Correct 540 ms 61184 KB Output is correct
9 Correct 1029 ms 66036 KB Output is correct
10 Correct 962 ms 62868 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12492 KB Output is correct
2 Correct 350 ms 21980 KB Output is correct
3 Correct 362 ms 22236 KB Output is correct
4 Correct 344 ms 22048 KB Output is correct
5 Correct 367 ms 22436 KB Output is correct
6 Correct 279 ms 22008 KB Output is correct
7 Correct 359 ms 22100 KB Output is correct
8 Correct 355 ms 22084 KB Output is correct
9 Correct 360 ms 22468 KB Output is correct
10 Correct 312 ms 22024 KB Output is correct
11 Correct 357 ms 22084 KB Output is correct
12 Correct 9 ms 12492 KB Output is correct
13 Correct 2084 ms 215084 KB Output is correct
14 Correct 3111 ms 218780 KB Output is correct
15 Correct 929 ms 212628 KB Output is correct
16 Correct 3795 ms 249372 KB Output is correct
17 Correct 3067 ms 220076 KB Output is correct
18 Correct 947 ms 61572 KB Output is correct
19 Correct 540 ms 61184 KB Output is correct
20 Correct 1029 ms 66036 KB Output is correct
21 Correct 962 ms 62868 KB Output is correct
22 Correct 2269 ms 216856 KB Output is correct
23 Correct 2455 ms 219504 KB Output is correct
24 Correct 3511 ms 220952 KB Output is correct
25 Correct 3496 ms 224752 KB Output is correct
26 Correct 3397 ms 220768 KB Output is correct
27 Correct 4172 ms 246604 KB Output is correct
28 Correct 1159 ms 216892 KB Output is correct
29 Correct 3524 ms 220300 KB Output is correct
30 Correct 3472 ms 219592 KB Output is correct
31 Correct 3445 ms 220356 KB Output is correct
32 Correct 1026 ms 67396 KB Output is correct
33 Correct 562 ms 61736 KB Output is correct
34 Correct 739 ms 59200 KB Output is correct
35 Correct 748 ms 59204 KB Output is correct
36 Correct 919 ms 60164 KB Output is correct
37 Correct 925 ms 60088 KB Output is correct