oj.uz

Submission #1103813

# Submission time Handle Problem Language Result Execution time Memory
1103813 2024-10-21T20:26:38 Z Thunnus Factories (JOI14_factories) C++17
100 / 100
 4034 ms 203344 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
using ll = long long;
const int mxN = (int)5e5+5;
const int mxLg = (int)20;
const ll LINF = (ll)3e18;
int n, sub[mxN], par[mxN], vis[mxN], lev[mxN];
ll best[mxN], dis[mxN][mxLg];
vector<pair<int,ll>> adj[mxN];

int fcen(int s, int p, int n){
    for(auto x : adj[s]){
        int u = x.fi;
        if(u!=p and sub[u]>n/2 and !vis[u])
            return fcen(u,s,n);
    }
    return s;
}

int dfs(int s, int p, int S, bool ok){
    sub[s]=1;
    for(auto x : adj[s]){
        int u = x.fi; ll w = x.se;
        if(u==p or vis[u]) continue;
        if(ok) dis[u][lev[u]-lev[S]]=dis[s][lev[s]-lev[S]]+w;
        sub[s]+=dfs(u,s, S,ok);
    }
    return sub[s];
}

void cen_decomp1(int s, int p){
    int n = dfs(s,p,s,0);
    int cen = fcen(s,p,n);
    vis[cen] = 1;
    if(p!=-1) lev[cen]=lev[p]+1;
    par[cen]=p;
    for(auto x : adj[cen]){
        int u = x.fi;
        if(u!=p and !vis[u])
            cen_decomp1(u,cen);
    }
}

void cen_decomp(int s, int p){
    int n = dfs(s,p,s,0);
    int cen = fcen(s,p,n);
    vis[cen] = 1; dfs(cen,p,cen,1);
    for(auto x : adj[cen]){
        int u = x.fi, w = x.se;
        if(u!=p and !vis[u]) cen_decomp(u,cen);
    }
}

void Init(int N, int a[], int b[], int d[]) {
    n = N; memset(par,-1,sizeof(par));
    for(int i = 0; i <= n; i++) best[i]=LINF;
    for(int i = 0; i < n-1; i++){
        adj[a[i]].pb({b[i],d[i]});
        adj[b[i]].pb({a[i],d[i]});
    }
    cen_decomp1(0,-1); fill(vis,vis+n,0); cen_decomp(0,-1);
}

ll Query(int s, int x[], int t, int y[]) {
    for(int i = 0; i < s; i++){
        int a = x[i], j = 0;
        while(a!=-1){
            ll DD = dis[x[i]][j];
            best[a]=min(best[a],DD), a = par[a], j++;
        }
    }
    ll ans = LINF;
    for(int i = 0; i < t; i++){
        int x = y[i], j = 0;
        while(x!=-1){
            ans = min(ans, dis[y[i]][j]+best[x]);
            x=par[x], j++;
        }
    }
    for(int i = 0; i < s; i++){
        int a = x[i];
        while(a!=-1) best[a]=LINF, a = par[a];
    }
    return ans;
}

Compilation message

factories.cpp: In function 'void cen_decomp(int, int)':
factories.cpp:53:23: warning: unused variable 'w' [-Wunused-variable]
   53 |         int u = x.fi, w = x.se;
      |                       ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14672 KB Output is correct
2 Correct 213 ms 32632 KB Output is correct
3 Correct 228 ms 32840 KB Output is correct
4 Correct 220 ms 32840 KB Output is correct
5 Correct 233 ms 33212 KB Output is correct
6 Correct 154 ms 32756 KB Output is correct
7 Correct 221 ms 32688 KB Output is correct
8 Correct 223 ms 32840 KB Output is correct
9 Correct 247 ms 35184 KB Output is correct
10 Correct 161 ms 34644 KB Output is correct
11 Correct 237 ms 34852 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14416 KB Output is correct
2 Correct 1579 ms 159312 KB Output is correct
3 Correct 2842 ms 163200 KB Output is correct
4 Correct 493 ms 156572 KB Output is correct
5 Correct 3876 ms 200144 KB Output is correct
6 Correct 2802 ms 165184 KB Output is correct
7 Correct 614 ms 62136 KB Output is correct
8 Correct 271 ms 61820 KB Output is correct
9 Correct 704 ms 67656 KB Output is correct
10 Correct 599 ms 63608 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14672 KB Output is correct
2 Correct 213 ms 32632 KB Output is correct
3 Correct 228 ms 32840 KB Output is correct
4 Correct 220 ms 32840 KB Output is correct
5 Correct 233 ms 33212 KB Output is correct
6 Correct 154 ms 32756 KB Output is correct
7 Correct 221 ms 32688 KB Output is correct
8 Correct 223 ms 32840 KB Output is correct
9 Correct 247 ms 35184 KB Output is correct
10 Correct 161 ms 34644 KB Output is correct
11 Correct 237 ms 34852 KB Output is correct
12 Correct 11 ms 14416 KB Output is correct
13 Correct 1579 ms 159312 KB Output is correct
14 Correct 2842 ms 163200 KB Output is correct
15 Correct 493 ms 156572 KB Output is correct
16 Correct 3876 ms 200144 KB Output is correct
17 Correct 2802 ms 165184 KB Output is correct
18 Correct 614 ms 62136 KB Output is correct
19 Correct 271 ms 61820 KB Output is correct
20 Correct 704 ms 67656 KB Output is correct
21 Correct 599 ms 63608 KB Output is correct
22 Correct 1775 ms 166424 KB Output is correct
23 Correct 1717 ms 170800 KB Output is correct
24 Correct 2894 ms 172832 KB Output is correct
25 Correct 3272 ms 175024 KB Output is correct
26 Correct 3099 ms 172424 KB Output is correct
27 Correct 4034 ms 203344 KB Output is correct
28 Correct 688 ms 166848 KB Output is correct
29 Correct 3211 ms 171876 KB Output is correct
30 Correct 3175 ms 171104 KB Output is correct
31 Correct 2914 ms 172988 KB Output is correct
32 Correct 689 ms 70444 KB Output is correct
33 Correct 231 ms 62132 KB Output is correct
34 Correct 455 ms 59348 KB Output is correct
35 Correct 460 ms 59540 KB Output is correct
36 Correct 602 ms 60612 KB Output is correct
37 Correct 604 ms 62792 KB Output is correct