oj.uz

Submission #393186

# Submission time Handle Problem Language Result Execution time Memory
393186 2021-04-22T22:52:36 Z jeroenodb Factories (JOI14_factories) C++14
100 / 100
 5259 ms 369320 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;
};
vector<anc> ancs[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].push_back({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();
        ancs[i].clear();
    }
    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) {
        for(auto& a : ancs[X[i]]) {
            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) {
        for(auto& a : ancs[Y[i]]) {
            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:22:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |     for(auto [to,w]: adj[at]) if(to!=from and !visited[to]) {
      |              ^
factories.cpp: In function 'void dfsd(int, int, ll)':
factories.cpp:29:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |     for(auto [to,w]: adj[at]) if(to!=from and !visited[to]) {
      |              ^
factories.cpp: In function 'int centroid(int)':
factories.cpp:38:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |         for(auto [to,w]: adj[at]) if(to!=from and !visited[to]) {
      |                  ^
factories.cpp: In function 'void decomp(int)':
factories.cpp:55:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |     for(auto [to,w]: adj[c]) if(!visited[to]) {
      |              ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24132 KB Output is correct
2 Correct 372 ms 32888 KB Output is correct
3 Correct 422 ms 43272 KB Output is correct
4 Correct 391 ms 42852 KB Output is correct
5 Correct 424 ms 43344 KB Output is correct
6 Correct 365 ms 42000 KB Output is correct
7 Correct 401 ms 42868 KB Output is correct
8 Correct 423 ms 42952 KB Output is correct
9 Correct 416 ms 43304 KB Output is correct
10 Correct 313 ms 41884 KB Output is correct
11 Correct 408 ms 43044 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24004 KB Output is correct
2 Correct 2721 ms 195220 KB Output is correct
3 Correct 3993 ms 284736 KB Output is correct
4 Correct 1095 ms 107852 KB Output is correct
5 Correct 4891 ms 366208 KB Output is correct
6 Correct 4162 ms 286084 KB Output is correct
7 Correct 1316 ms 82884 KB Output is correct
8 Correct 673 ms 59860 KB Output is correct
9 Correct 1432 ms 96828 KB Output is correct
10 Correct 1349 ms 84292 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24132 KB Output is correct
2 Correct 372 ms 32888 KB Output is correct
3 Correct 422 ms 43272 KB Output is correct
4 Correct 391 ms 42852 KB Output is correct
5 Correct 424 ms 43344 KB Output is correct
6 Correct 365 ms 42000 KB Output is correct
7 Correct 401 ms 42868 KB Output is correct
8 Correct 423 ms 42952 KB Output is correct
9 Correct 416 ms 43304 KB Output is correct
10 Correct 313 ms 41884 KB Output is correct
11 Correct 408 ms 43044 KB Output is correct
12 Correct 18 ms 24004 KB Output is correct
13 Correct 2721 ms 195220 KB Output is correct
14 Correct 3993 ms 284736 KB Output is correct
15 Correct 1095 ms 107852 KB Output is correct
16 Correct 4891 ms 366208 KB Output is correct
17 Correct 4162 ms 286084 KB Output is correct
18 Correct 1316 ms 82884 KB Output is correct
19 Correct 673 ms 59860 KB Output is correct
20 Correct 1432 ms 96828 KB Output is correct
21 Correct 1349 ms 84292 KB Output is correct
22 Correct 3137 ms 219608 KB Output is correct
23 Correct 3260 ms 224764 KB Output is correct
24 Correct 4543 ms 292516 KB Output is correct
25 Correct 4615 ms 297012 KB Output is correct
26 Correct 4633 ms 293372 KB Output is correct
27 Correct 5259 ms 369320 KB Output is correct
28 Correct 1352 ms 118300 KB Output is correct
29 Correct 4500 ms 292472 KB Output is correct
30 Correct 4511 ms 292028 KB Output is correct
31 Correct 4566 ms 292560 KB Output is correct
32 Correct 1349 ms 97528 KB Output is correct
33 Correct 558 ms 60512 KB Output is correct
34 Correct 960 ms 75316 KB Output is correct
35 Correct 987 ms 76108 KB Output is correct
36 Correct 1226 ms 81184 KB Output is correct
37 Correct 1220 ms 81376 KB Output is correct