oj.uz

Submission #894657

# Submission time Handle Problem Language Result Execution time Memory
894657 2023-12-28T15:41:28 Z ttamx Factories (JOI14_factories) C++14
100 / 100
 3852 ms 192596 KB 
#include "factories.h"
#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const ll INF=LLONG_MAX/2;

int n;
vector<vector<pair<int,int>>> adj;
vector<int> sz,lv,pa;
vector<bool> used;
vector<vector<ll>> dist;
vector<ll> dp;

int dfssz(int u,int p=-1){
    sz[u]=1;
    for(auto [v,w]:adj[u])if(v!=p&&!used[v])sz[u]+=dfssz(v,u);
    return sz[u];
}

int centroid(int u,int cnt,int p=-1){
    for(auto [v,w]:adj[u])if(v!=p&&!used[v]&&sz[v]>cnt/2)return centroid(v,cnt,u);
    return u;
}

void filldist(int u,int l,ll d,int p=-1){
    dist[l][u]=d;
    for(auto [v,w]:adj[u])if(v!=p&&!used[v])filldist(v,l,d+w,u);
}

void decom(int u,int p=-1,int l=0){
    u=centroid(u,dfssz(u));
    pa[u]=p;
    lv[u]=l;
    used[u]=true;
    if(l==dist.size())dist.emplace_back(vector<ll>(n));
    for(auto [v,w]:adj[u])if(!used[v])filldist(v,l,w);
    for(auto [v,w]:adj[u])if(!used[v])decom(v,u,l+1);
}

void update(int st){
    for(int u=st;u!=-1;u=pa[u])dp[u]=min(dp[u],dist[lv[u]][st]);
}

ll query(int st){
    ll res=INF;
    for(int u=st;u!=-1;u=pa[u])res=min(res,dist[lv[u]][st]+dp[u]);
    return res;
}

void clear(int st){
    for(int u=st;u!=-1;u=pa[u])dp[u]=INF;
}

void Init(int N, int A[], int B[], int D[]){
    n=N;
    adj.assign(n,{});
    sz=lv=pa=vector<int>(n);
    used.assign(n,0);
    dp.assign(n,INF);
    for(int i=0;i<n-1;i++){
        int u=A[i],v=B[i],w=D[i];
        adj[u].emplace_back(v,w);
        adj[v].emplace_back(u,w);
    }
    decom(1);
}

ll Query(int S, int X[], int T, int Y[]) {
    ll ans=INF;
    for(int i=0;i<S;i++)update(X[i]);
    for(int i=0;i<T;i++)ans=min(ans,query(Y[i]));
    for(int i=0;i<S;i++)clear(X[i]);
    return ans;
}

Compilation message

factories.cpp: In function 'int dfssz(int, int)':
factories.cpp:19:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |     for(auto [v,w]:adj[u])if(v!=p&&!used[v])sz[u]+=dfssz(v,u);
      |              ^
factories.cpp: In function 'int centroid(int, int, int)':
factories.cpp:24:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |     for(auto [v,w]:adj[u])if(v!=p&&!used[v]&&sz[v]>cnt/2)return centroid(v,cnt,u);
      |              ^
factories.cpp: In function 'void filldist(int, int, ll, int)':
factories.cpp:30:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |     for(auto [v,w]:adj[u])if(v!=p&&!used[v])filldist(v,l,d+w,u);
      |              ^
factories.cpp: In function 'void decom(int, int, int)':
factories.cpp:38:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     if(l==dist.size())dist.emplace_back(vector<ll>(n));
      |        ~^~~~~~~~~~~~~
factories.cpp:39:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |     for(auto [v,w]:adj[u])if(!used[v])filldist(v,l,w);
      |              ^
factories.cpp:40:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |     for(auto [v,w]:adj[u])if(!used[v])decom(v,u,l+1);
      |              ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16984 KB Output is correct
2 Correct 275 ms 29268 KB Output is correct
3 Correct 269 ms 29300 KB Output is correct
4 Correct 271 ms 29416 KB Output is correct
5 Correct 267 ms 29372 KB Output is correct
6 Correct 166 ms 30192 KB Output is correct
7 Correct 254 ms 30552 KB Output is correct
8 Correct 252 ms 30524 KB Output is correct
9 Correct 293 ms 30780 KB Output is correct
10 Correct 156 ms 30120 KB Output is correct
11 Correct 253 ms 30824 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 1465 ms 143188 KB Output is correct
3 Correct 2246 ms 157172 KB Output is correct
4 Correct 462 ms 89092 KB Output is correct
5 Correct 3111 ms 186316 KB Output is correct
6 Correct 2354 ms 158492 KB Output is correct
7 Correct 759 ms 56400 KB Output is correct
8 Correct 235 ms 44300 KB Output is correct
9 Correct 828 ms 61028 KB Output is correct
10 Correct 793 ms 56800 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16984 KB Output is correct
2 Correct 275 ms 29268 KB Output is correct
3 Correct 269 ms 29300 KB Output is correct
4 Correct 271 ms 29416 KB Output is correct
5 Correct 267 ms 29372 KB Output is correct
6 Correct 166 ms 30192 KB Output is correct
7 Correct 254 ms 30552 KB Output is correct
8 Correct 252 ms 30524 KB Output is correct
9 Correct 293 ms 30780 KB Output is correct
10 Correct 156 ms 30120 KB Output is correct
11 Correct 253 ms 30824 KB Output is correct
12 Correct 3 ms 16728 KB Output is correct
13 Correct 1465 ms 143188 KB Output is correct
14 Correct 2246 ms 157172 KB Output is correct
15 Correct 462 ms 89092 KB Output is correct
16 Correct 3111 ms 186316 KB Output is correct
17 Correct 2354 ms 158492 KB Output is correct
18 Correct 759 ms 56400 KB Output is correct
19 Correct 235 ms 44300 KB Output is correct
20 Correct 828 ms 61028 KB Output is correct
21 Correct 793 ms 56800 KB Output is correct
22 Correct 1695 ms 147028 KB Output is correct
23 Correct 1890 ms 149496 KB Output is correct
24 Correct 2803 ms 159716 KB Output is correct
25 Correct 3026 ms 160000 KB Output is correct
26 Correct 2951 ms 159508 KB Output is correct
27 Correct 3852 ms 192596 KB Output is correct
28 Correct 526 ms 91636 KB Output is correct
29 Correct 2775 ms 158452 KB Output is correct
30 Correct 2876 ms 159180 KB Output is correct
31 Correct 2560 ms 159848 KB Output is correct
32 Correct 791 ms 60092 KB Output is correct
33 Correct 231 ms 42604 KB Output is correct
34 Correct 453 ms 51520 KB Output is correct
35 Correct 516 ms 51360 KB Output is correct
36 Correct 729 ms 53608 KB Output is correct
37 Correct 672 ms 53780 KB Output is correct