oj.uz

Submission #1000296

# Submission time Handle Problem Language Result Execution time Memory
1000296 2024-06-17T08:14:21 Z MarwenElarbi Factories (JOI14_factories) C++17
100 / 100
 2904 ms 351660 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=5e5+5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<pair<int,int>> adj[nax];
int sz[nax];
bool removed[nax];
vector<pair<int,ll>> parent[nax];
long long ans[nax];
int get_sz(int x,int p){
    sz[x]=1;
    for(auto u:adj[x]){
        if(u.fi==p||removed[u.fi]) continue;
        sz[x]+=get_sz(u.fi,x);
    }
    return sz[x];
}
int get_centroid(int x,int t_sz,int p){
    for(auto u:adj[x]){
        if(u.fi==p||removed[u.fi]) continue;
        if(sz[u.fi]*2>t_sz) return get_centroid(u.fi,t_sz,x);
    }
    return x;
}
void get_dist(int x,int centroid,int p,long long cur){
    for(auto u:adj[x]){
        if(u.fi==p||removed[u.fi]) continue;
        cur+=u.se;
        get_dist(u.fi,centroid,x,cur);
        cur-=u.se;
    }
    parent[x].pb({centroid,cur});
    return;
}
void build(int x){
    int centroid=get_centroid(x,get_sz(x,-1),-1);
    for(auto u:adj[centroid]){
        if(removed[u.fi]) continue;
        get_dist(u.fi,centroid,centroid,u.se);
    }
    removed[centroid]=1;
    for(auto u:adj[centroid]){
        if(removed[u.fi]) continue;
        build(u.fi);
    }
    return;
}
void paint(int x){
    for(auto u:parent[x]){
        ans[u.fi]=min(ans[u.fi],u.se);
    }
    ans[x]=0;
    return;
}
void init_paint(int x){
    for(auto u:parent[x]){
        ans[u.fi]=1e18;
    }
    ans[x]=1e18;
    return;
}
long long get_ans(int x){
    ll res=ans[x];
    for(auto u:parent[x]){
        res=min(res,u.se+ans[u.fi]);
    }
    return res;
}
void Init(int N, int A[], int B[], int D[]) {
    int n=N;
    for (int i = 0; i < n; ++i) ans[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]});
    }
    build(0);
    return;
}
long long Query(int S, int X[], int T, int Y[]){
    for (int i = 0; i < T; ++i)
    {
        paint(Y[i]);
    }
    ll res=1e18;
    for (int i = 0; i < S; ++i)
    {
        res=min(res,get_ans(X[i]));
    }
    for (int i = 0; i < T; ++i)
    {
        init_paint(Y[i]);
    }
    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 45660 KB Output is correct
2 Correct 173 ms 59888 KB Output is correct
3 Correct 196 ms 60404 KB Output is correct
4 Correct 197 ms 60400 KB Output is correct
5 Correct 213 ms 61012 KB Output is correct
6 Correct 134 ms 59472 KB Output is correct
7 Correct 195 ms 60496 KB Output is correct
8 Correct 202 ms 60496 KB Output is correct
9 Correct 207 ms 60928 KB Output is correct
10 Correct 133 ms 59496 KB Output is correct
11 Correct 192 ms 60416 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 45660 KB Output is correct
2 Correct 1174 ms 207976 KB Output is correct
3 Correct 1817 ms 252600 KB Output is correct
4 Correct 370 ms 106944 KB Output is correct
5 Correct 2469 ms 347904 KB Output is correct
6 Correct 1854 ms 253264 KB Output is correct
7 Correct 486 ms 97956 KB Output is correct
8 Correct 223 ms 73708 KB Output is correct
9 Correct 508 ms 103760 KB Output is correct
10 Correct 515 ms 98640 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 45660 KB Output is correct
2 Correct 173 ms 59888 KB Output is correct
3 Correct 196 ms 60404 KB Output is correct
4 Correct 197 ms 60400 KB Output is correct
5 Correct 213 ms 61012 KB Output is correct
6 Correct 134 ms 59472 KB Output is correct
7 Correct 195 ms 60496 KB Output is correct
8 Correct 202 ms 60496 KB Output is correct
9 Correct 207 ms 60928 KB Output is correct
10 Correct 133 ms 59496 KB Output is correct
11 Correct 192 ms 60416 KB Output is correct
12 Correct 7 ms 45660 KB Output is correct
13 Correct 1174 ms 207976 KB Output is correct
14 Correct 1817 ms 252600 KB Output is correct
15 Correct 370 ms 106944 KB Output is correct
16 Correct 2469 ms 347904 KB Output is correct
17 Correct 1854 ms 253264 KB Output is correct
18 Correct 486 ms 97956 KB Output is correct
19 Correct 223 ms 73708 KB Output is correct
20 Correct 508 ms 103760 KB Output is correct
21 Correct 515 ms 98640 KB Output is correct
22 Correct 1377 ms 209604 KB Output is correct
23 Correct 1351 ms 215228 KB Output is correct
24 Correct 2295 ms 257792 KB Output is correct
25 Correct 2188 ms 259664 KB Output is correct
26 Correct 2062 ms 258524 KB Output is correct
27 Correct 2904 ms 351660 KB Output is correct
28 Correct 454 ms 113336 KB Output is correct
29 Correct 2171 ms 258132 KB Output is correct
30 Correct 2090 ms 258388 KB Output is correct
31 Correct 1978 ms 258168 KB Output is correct
32 Correct 570 ms 103764 KB Output is correct
33 Correct 207 ms 73692 KB Output is correct
34 Correct 326 ms 88400 KB Output is correct
35 Correct 343 ms 89460 KB Output is correct
36 Correct 490 ms 97052 KB Output is correct
37 Correct 475 ms 97104 KB Output is correct