oj.uz

Submission #930954

# Submission time Handle Problem Language Result Execution time Memory
930954 2024-02-20T23:12:18 Z idiotcomputer Factories (JOI14_factories) C++11
100 / 100
 4045 ms 377432 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define pb push_back
#define ll long long int 
#define pii pair<int,ll>
#define f first 
#define s second 

const int mxN = 5*1e5;
const ll llmax = (ll) 1e17;

vector<pii> adj[mxN];
vector<pii> ctree[mxN];

int ssize[mxN];
ll res[mxN];
bool vis[mxN];

void dfs(int node, int p){
    ssize[node] = 1;
    for (pii next : adj[node]){
        if (next.f == p || vis[next.f]){
            continue;
        }
        dfs(next.f,node);
        ssize[node] += ssize[next.f];
    }
}

void dfs2(int node, int p, int cent, ll cdepth){
    ctree[node].pb({cent,cdepth});
    for (pii next : adj[node]){
        if (next.f == p || vis[next.f]){
            continue;
        }
        dfs2(next.f,node,cent,cdepth+next.s);
    }
}

int gcentroid(int node, int p, int tot){
    for (pii next : adj[node]){
        if (next.f == p || vis[next.f]){
            continue;
        }
        if (ssize[next.f] > tot){
            return gcentroid(next.f,node,tot);
        }
    }
    return node;
}

void cdecomp(int node){
    dfs(node,-1);
    int centroid = gcentroid(node,-1,ssize[node]/2);
    dfs2(centroid,-1,centroid,0);
    vis[centroid] = 1;
    for (pii next : adj[centroid]){
        if (!vis[next.f]){
            cdecomp(next.f);
        }
    }
}

void upd(int node, bool w){
    for (pii next : ctree[node]){
        if (w){
            res[next.f] = min(res[next.f],next.s);
        } else {
            res[next.f] = llmax;
        }
    }
}

ll query(int node){
    ll tot = llmax;
    for (pii next : ctree[node]){
        tot = min(tot, next.s + res[next.f]);
    }
    return tot;
}

void Init(int N, int A[], int B[], int D[]){
    for (int i =0; i < N-1; i++){
        adj[A[i]].pb({B[i],D[i]});
        adj[B[i]].pb({A[i],D[i]});
    }
    memset(vis,0,sizeof(vis));
    cdecomp(0);
    for (int i = 0; i < N; i++){
        res[i] = llmax;
    }
}

long long Query(int S, int X[], int T, int Y[]){
    vector<int> temp;
    ll tot = llmax;
    for (int i = 0; i < S; i++){
        upd(X[i],true);
        temp.pb(X[i]);
    }
    for (int i = 0; i < T; i++){
        tot = min(tot, query(Y[i]));
    }
    for (int i =0; i < S; i++){
        upd(temp[i],false);
    }
    return tot;
}
/*
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n,q;
    cin >> n >> q;
    
    int a,b,d;
    for (int i =0; i < n-1; i++){
        cin >> a >> b >> d;
        adj[a].pb({b,d});
        adj[b].pb({a,d});
    }
   
    memset(vis,0,sizeof(vis));
    cdecomp(0);
    for (int i = 0; i < n; i++){
        res[i] = llmax;
    }

    int s,t;
    ll tot;
    vector<int> temp;
    for (int i =0; i < q; i++){
        cin >> s >> t;
        tot = llmax;
        temp.clear();
        for (int j = 0; j < s; j++){
            cin >> a;
            upd(a,true);
            temp.pb(a);
        }
        for (int j = 0; j < t; j++){
            cin >> a;
            tot = min(tot, query(a));
        }
        for (int j =0; j < s; j++){
            upd(temp[j],false);
        }
        cout << tot << '\n';
    }
    
    
    return 0;
}*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 45916 KB Output is correct
2 Correct 204 ms 60256 KB Output is correct
3 Correct 221 ms 61036 KB Output is correct
4 Correct 211 ms 60752 KB Output is correct
5 Correct 221 ms 61264 KB Output is correct
6 Correct 159 ms 59868 KB Output is correct
7 Correct 213 ms 60752 KB Output is correct
8 Correct 209 ms 60756 KB Output is correct
9 Correct 223 ms 61264 KB Output is correct
10 Correct 157 ms 59984 KB Output is correct
11 Correct 213 ms 60640 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 45656 KB Output is correct
2 Correct 1877 ms 225428 KB Output is correct
3 Correct 2694 ms 297104 KB Output is correct
4 Correct 653 ms 118696 KB Output is correct
5 Correct 3447 ms 377432 KB Output is correct
6 Correct 2827 ms 297340 KB Output is correct
7 Correct 659 ms 98152 KB Output is correct
8 Correct 254 ms 73920 KB Output is correct
9 Correct 870 ms 110960 KB Output is correct
10 Correct 658 ms 98544 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 45916 KB Output is correct
2 Correct 204 ms 60256 KB Output is correct
3 Correct 221 ms 61036 KB Output is correct
4 Correct 211 ms 60752 KB Output is correct
5 Correct 221 ms 61264 KB Output is correct
6 Correct 159 ms 59868 KB Output is correct
7 Correct 213 ms 60752 KB Output is correct
8 Correct 209 ms 60756 KB Output is correct
9 Correct 223 ms 61264 KB Output is correct
10 Correct 157 ms 59984 KB Output is correct
11 Correct 213 ms 60640 KB Output is correct
12 Correct 10 ms 45656 KB Output is correct
13 Correct 1877 ms 225428 KB Output is correct
14 Correct 2694 ms 297104 KB Output is correct
15 Correct 653 ms 118696 KB Output is correct
16 Correct 3447 ms 377432 KB Output is correct
17 Correct 2827 ms 297340 KB Output is correct
18 Correct 659 ms 98152 KB Output is correct
19 Correct 254 ms 73920 KB Output is correct
20 Correct 870 ms 110960 KB Output is correct
21 Correct 658 ms 98544 KB Output is correct
22 Correct 2191 ms 228256 KB Output is correct
23 Correct 2255 ms 231952 KB Output is correct
24 Correct 3389 ms 301276 KB Output is correct
25 Correct 3531 ms 303896 KB Output is correct
26 Correct 3249 ms 302212 KB Output is correct
27 Correct 4045 ms 376056 KB Output is correct
28 Correct 829 ms 125488 KB Output is correct
29 Correct 3074 ms 301388 KB Output is correct
30 Correct 3224 ms 300828 KB Output is correct
31 Correct 3012 ms 301396 KB Output is correct
32 Correct 895 ms 111156 KB Output is correct
33 Correct 246 ms 74432 KB Output is correct
34 Correct 529 ms 90944 KB Output is correct
35 Correct 508 ms 91728 KB Output is correct
36 Correct 747 ms 97104 KB Output is correct
37 Correct 749 ms 97200 KB Output is correct