oj.uz

Submission #589611

# Submission time Handle Problem Language Result Execution time Memory
589611 2022-07-04T22:26:13 Z perchuts Factories (JOI14_factories) C++17
100 / 100
 3383 ms 196304 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 5e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

vector<pair<int,ll>>g[maxn];

int n, subt[maxn], vis[maxn], par[maxn], lvl[maxn];

ll dist[maxn][20], best[maxn];

int dfs(int u,int p,int lvl,int d){
    if(lvl!=-1)dist[u][lvl] = dist[p][lvl]+d;
    subt[u] = 1;
    for(auto [v,w]:g[u]){
        if(v==p||vis[v])continue;
        subt[u] += dfs(v,u,lvl,w);
    }
    return subt[u];
}

int find_centroid(int u,int p,int tam){
    for(auto [v,d]:g[u]){
        if(vis[v]||v==p)continue;
        if(subt[v]*2>tam)return find_centroid(v,u,tam);
    }
    return u;
}

void centroid_decomposition(int u=1,int p=-1,int w=0){
    int c = find_centroid(u,p, dfs(u,p,p==-1?-1:lvl[p],w) );
    vis[c] = 1, par[c] = p;
    if(p!=-1)lvl[c] = lvl[p] + 1;
    for(auto [v,w]:g[c]){
        if(vis[v])continue;
        centroid_decomposition(v,c,w);
    }
}

void Init(int N,int a[],int b[],int d[]) {
    n = N;
    for(int i=0;i<n-1;++i){
        ++a[i], ++b[i];
        g[a[i]].pb({b[i],d[i]});
        g[b[i]].pb({a[i],d[i]});
    }
    centroid_decomposition();
    for(int i=1;i<=n;++i)best[i] = 1e18;
}

ll distance(int u,int v){
    int su = u, sv = v;
    if(lvl[u]<lvl[v])swap(u,v), swap(su,sv);
    while(lvl[u]!=lvl[v])u = par[u];
    while(u!=v)u = par[u], v = par[v];
    return dist[su][lvl[u]] + dist[sv][lvl[u]];
}

void update(int u, bool type){
    int cur = u;
    while(cur!=-1){
        if(type)ckmin(best[cur],dist[u][lvl[cur]]);
        else best[cur] = 1e18;
        cur = par[cur];
    }
}

ll query(int u){
    ll resp = best[u];
    int cur = par[u];
    while(cur!=-1){
        ckmin(resp,best[cur]+distance(u,cur));
        cur = par[cur];
    }
    return resp;
}

long long Query(int S,int X[], int T,int Y[]) {
    for(int i=0;i<T;++i){
        update(Y[i]+1,1);
    }
    ll ans = 1e18;
    for(int i=0;i<S;++i){
        ckmin(ans,query(X[i]+1));
    }
    for(int i=0;i<T;++i)update(Y[i]+1,0);
    return ans;
}

// int main(){
//     int n,q;cin>>n>>q;
//     vector<int>a,b,d;
//     for(int i=0;i<n-1;++i){
//         int x,y,z;cin>>x>>y>>z;
//         a.pb(x), b.pb(y), d.pb(z);
//     }
//     vector<vector<int>>s, t;
//     for(int i=0;i<q;++i){
//         vector<int>sc, tc;
//         int x,y;cin>>x>>y;
//         for(int j=0;j<x;++j){
//             int z;cin>>z;
//             sc.pb(z);
//         }
//         for(int j=0;j<y;++j){
//             int z;cin>>z;
//             tc.pb(z);
//         }
//         s.pb(sc), t.pb(tc);
//     }
//     Init(n,a,b,d);
//     for(int i=0;i<q;++i){
//         cout<<Query(sz(s[i]),s[i],sz(t[i]),t[i])<<endl;
//     }
// }

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12628 KB Output is correct
2 Correct 265 ms 30748 KB Output is correct
3 Correct 317 ms 30780 KB Output is correct
4 Correct 334 ms 30788 KB Output is correct
5 Correct 394 ms 31096 KB Output is correct
6 Correct 229 ms 30796 KB Output is correct
7 Correct 308 ms 30796 KB Output is correct
8 Correct 320 ms 30788 KB Output is correct
9 Correct 352 ms 31100 KB Output is correct
10 Correct 179 ms 30800 KB Output is correct
11 Correct 311 ms 30896 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12244 KB Output is correct
2 Correct 1396 ms 159148 KB Output is correct
3 Correct 2150 ms 162420 KB Output is correct
4 Correct 547 ms 156532 KB Output is correct
5 Correct 2901 ms 193444 KB Output is correct
6 Correct 2144 ms 164512 KB Output is correct
7 Correct 883 ms 60604 KB Output is correct
8 Correct 353 ms 60288 KB Output is correct
9 Correct 985 ms 65120 KB Output is correct
10 Correct 851 ms 61864 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12628 KB Output is correct
2 Correct 265 ms 30748 KB Output is correct
3 Correct 317 ms 30780 KB Output is correct
4 Correct 334 ms 30788 KB Output is correct
5 Correct 394 ms 31096 KB Output is correct
6 Correct 229 ms 30796 KB Output is correct
7 Correct 308 ms 30796 KB Output is correct
8 Correct 320 ms 30788 KB Output is correct
9 Correct 352 ms 31100 KB Output is correct
10 Correct 179 ms 30800 KB Output is correct
11 Correct 311 ms 30896 KB Output is correct
12 Correct 11 ms 12244 KB Output is correct
13 Correct 1396 ms 159148 KB Output is correct
14 Correct 2150 ms 162420 KB Output is correct
15 Correct 547 ms 156532 KB Output is correct
16 Correct 2901 ms 193444 KB Output is correct
17 Correct 2144 ms 164512 KB Output is correct
18 Correct 883 ms 60604 KB Output is correct
19 Correct 353 ms 60288 KB Output is correct
20 Correct 985 ms 65120 KB Output is correct
21 Correct 851 ms 61864 KB Output is correct
22 Correct 1808 ms 166400 KB Output is correct
23 Correct 1812 ms 168992 KB Output is correct
24 Correct 2784 ms 170348 KB Output is correct
25 Correct 2946 ms 174488 KB Output is correct
26 Correct 2534 ms 170600 KB Output is correct
27 Correct 3383 ms 196304 KB Output is correct
28 Correct 724 ms 166884 KB Output is correct
29 Correct 2614 ms 170264 KB Output is correct
30 Correct 2694 ms 169652 KB Output is correct
31 Correct 2782 ms 170216 KB Output is correct
32 Correct 1064 ms 66284 KB Output is correct
33 Correct 306 ms 60564 KB Output is correct
34 Correct 623 ms 57804 KB Output is correct
35 Correct 648 ms 57944 KB Output is correct
36 Correct 868 ms 58992 KB Output is correct
37 Correct 805 ms 58920 KB Output is correct