oj.uz

Submission #398112

# Submission time Handle Problem Language Result Execution time Memory
398112 2021-05-03T17:23:31 Z bonopo Factories (JOI14_factories) C++17
15 / 100
 8000 ms 94708 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define el "\n"
#define f first
#define s second

#pragma GCC optimize("O3")
#pragma GCC target("sse4")

typedef long long ll;
const ll MM=5e5+5, MOD=1e9+7;
int top[MM], dep[MM], fa[MM], son[MM], sz[MM], nxt[MM]; ll dst[MM], spc[MM];
vector<pair<int,int>> adj[MM];
bool blk[MM];

void df1(int u, int pa) {
    sz[u]=1; fa[u]=pa; dep[u]=dep[pa]+1;
    for(pair<int,int> &e:adj[u]) {
        int v=e.f, w=e.s; if(v==pa) continue;
        dst[v]=dst[u]+w; df1(v, u); sz[u]+=sz[v];
        if(sz[v]>sz[son[u]]) son[u]=v; } }
void df2(int u, int pa) {
    if(son[u]) {
        top[son[u]]=top[u]; df2(son[u], u); }
    for(pair<int,int> &e:adj[u]) {
        int v=e.f; if(v==pa||v==son[u]) continue;
        df2(top[v]=v, u); } }
inline int lca(int u, int v) {
    for(; top[u]!=top[v]; u=fa[top[u]]) {
        if(dep[top[u]]<dep[top[v]]) swap(u, v); }
    return dep[u]<dep[v]?u:v; }
void gsz(int u, int pa) {
    sz[u]=1;
    for(pair<int,int> &e:adj[u]) {
        int v=e.f; if(blk[v]||v==pa) continue;
        gsz(v, u); sz[u]+=sz[v]; } }
int ctr(int u, int pa, int nd) {
    for(pair<int,int> &e:adj[u]) {
        int v=e.f; if(blk[v]||pa==v) continue;
        if(sz[v]*2>nd) return ctr(v, u, nd); }
    return u; }
inline ll dist(int u, int v) {
    return dst[u]+dst[v]-2LL*dst[lca(u, v)]; }
void slv(int u, int pa) {
    gsz(u, -1); u=ctr(u, -1, sz[u]); blk[u]=1; nxt[u]=pa;
    for(pair<int,int> &e:adj[u]) {
        int v=e.f; if(!blk[v]) slv(v, u); } }
void Init(int N, int A[], int B[], int D[]) {
    for(int i=0; i<N; ++i) spc[i]=1e18;
    for(int i=0; i<N-1; ++i) {
        adj[A[i]].pb({B[i], D[i]}); adj[B[i]].pb({A[i], D[i]}); }
    df1(0, 0); df2(top[0]=0, 0); slv(0, -1); }
long long Query(int S, int X[], int T, int Y[]) {
    for(int i=0, c; i<S; ++i) {
        c=X[i];
        while(c!=-1)
            spc[c]=min(spc[c], dist(X[i], c)), c=nxt[c], assert(c!=nxt[c]); }
    long long ans=1e18;
    for(int i=0, c; i<T; ++i) {
        c=Y[i];
        while(c!=-1)
            ans=min(ans, dist(Y[i], c)+spc[c]), c=nxt[c], assert(c!=nxt[c]); }
    for(int i=0, c; i<S; ++i) {
        c=X[i];
        while(c!=-1)
            spc[c]=1e18, c=nxt[c], assert(c!=nxt[c]); }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12364 KB Output is correct
2 Correct 498 ms 29924 KB Output is correct
3 Correct 598 ms 29980 KB Output is correct
4 Correct 579 ms 30068 KB Output is correct
5 Correct 3031 ms 30368 KB Output is correct
6 Correct 299 ms 29980 KB Output is correct
7 Correct 591 ms 30076 KB Output is correct
8 Correct 617 ms 30028 KB Output is correct
9 Correct 3021 ms 30308 KB Output is correct
10 Correct 288 ms 29928 KB Output is correct
11 Correct 599 ms 30104 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12236 KB Output is correct
2 Correct 2215 ms 66676 KB Output is correct
3 Correct 2726 ms 83984 KB Output is correct
4 Correct 834 ms 73056 KB Output is correct
5 Execution timed out 8087 ms 94708 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12364 KB Output is correct
2 Correct 498 ms 29924 KB Output is correct
3 Correct 598 ms 29980 KB Output is correct
4 Correct 579 ms 30068 KB Output is correct
5 Correct 3031 ms 30368 KB Output is correct
6 Correct 299 ms 29980 KB Output is correct
7 Correct 591 ms 30076 KB Output is correct
8 Correct 617 ms 30028 KB Output is correct
9 Correct 3021 ms 30308 KB Output is correct
10 Correct 288 ms 29928 KB Output is correct
11 Correct 599 ms 30104 KB Output is correct
12 Correct 11 ms 12236 KB Output is correct
13 Correct 2215 ms 66676 KB Output is correct
14 Correct 2726 ms 83984 KB Output is correct
15 Correct 834 ms 73056 KB Output is correct
16 Execution timed out 8087 ms 94708 KB Time limit exceeded
17 Halted 0 ms 0 KB -