oj.uz

Submission #708475

# Submission time Handle Problem Language Result Execution time Memory
708475 2023-03-11T20:04:02 Z Dan4Life Factories (JOI14_factories) C++17
0 / 100
 3644 ms 152172 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+10;
const int mxLg = (int)22;
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) continue;
        if(ok) dis[u][lev[u]-lev[S]]=dis[s][lev[s]-lev[S]]+w;
        if(!vis[u]) 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];
            //cout << x[i] << " " << a << " " << DD << "\n";
            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;
}
/*
7 3
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
2 2
0 6
3 4
3 2
0 1 3
4 6
1 1
2
5

10 2
0 1 2
0 5 3
1 2 4
1 3 1
5 6 7
5 8 5
5 9 6
3 4 2
6 7 4
5 5
0 1 2 3 4
5 6 7 8 9
5 5
5 6 7 8 9
0 1 2 3 4
*/

Compilation message

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

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14420 KB Output is correct
2 Correct 243 ms 23344 KB Output is correct
3 Correct 263 ms 23264 KB Output is correct
4 Correct 273 ms 23416 KB Output is correct
5 Incorrect 268 ms 23632 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14164 KB Output is correct
2 Correct 2024 ms 148348 KB Output is correct
3 Incorrect 3644 ms 152172 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14420 KB Output is correct
2 Correct 243 ms 23344 KB Output is correct
3 Correct 263 ms 23264 KB Output is correct
4 Correct 273 ms 23416 KB Output is correct
5 Incorrect 268 ms 23632 KB Output isn't correct
6 Halted 0 ms 0 KB -