oj.uz

Submission #1109004

# Submission time Handle Problem Language Result Execution time Memory
1109004 2024-11-05T18:42:11 Z doducanh Factories (JOI14_factories) C++14
100 / 100
 3168 ms 355716 KB 
#include <bits/stdc++.h>
//#include "factories.h"
using namespace std;
#define ll long long
#define fi first
#define se second
const ll MOD = 1e9 + 7;
const ll N = 5e5 + 2;
const ll inf = 1e14 + 2;

vector<ll> minn(N);
vector<int> sz(N), used(N, 0);
vector<vector<pair<int, ll>>> adj(N), ancestors(N);

int n;
int dfs(int u,int par)
{
    sz[u]=1;
    for(pair<int,ll>pp:adj[u]){
        int v=pp.fi;
        int w=pp.se;
        if(v==par||used[v])continue;
        sz[u]+=dfs(v,u);
    }
    return sz[u];
}
void update(int node, int parent, int c, ll d) {
    ancestors[node].push_back(make_pair(c, d));
    for (auto child : adj[node]) {
        if (child.first == parent || used[child.first]) continue;
        update(child.first, node, c, d + child.second);
    }
}

void find_cent(int node, int parent, int size) {
    for (auto child : adj[node]) {
        if (child.first == parent || used[child.first]) continue;
        if (sz[child.first] * 2 > size) {
            find_cent(child.first, node, size);
            return;
        }
    }
    update(node, -1, node, 0);
    used[node] = 1;
    for (auto child :adj[node]) {
        if (used[child.first]) continue;
        find_cent(child.first, node,dfs(child.fi,node));
    }
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N-1; i++) {
        adj[A[i]].push_back(make_pair(B[i], D[i]));
        adj[B[i]].push_back(make_pair(A[i], D[i]));
    }
    dfs(0, -1);
    find_cent(0, -1, N);
}
long long Query(int S, int X[], int T, int Y[])
{
    for(int i=0;i<T;i++){
        for(pair<int,long long> y:ancestors[Y[i]]){
            minn[y.fi]=inf;
        }
    }
    for(int i=0;i<S;i++){
        for(pair<int,ll> y:ancestors[X[i]]){
            minn[y.fi]=min(minn[y.fi],y.se);
        }
    }
    ll ans=inf;
    for(int i=0;i<T;i++){
        for(pair<int,ll> y:ancestors[Y[i]]){
            ans=min(ans,minn[y.fi]+y.se);
        }
    }
    return ans;
}

Compilation message

factories.cpp: In function 'int dfs(int, int)':
factories.cpp:21:13: warning: unused variable 'w' [-Wunused-variable]
   21 |         int w=pp.se;
      |             ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 48208 KB Output is correct
2 Correct 221 ms 53320 KB Output is correct
3 Correct 221 ms 53832 KB Output is correct
4 Correct 230 ms 58696 KB Output is correct
5 Correct 238 ms 52040 KB Output is correct
6 Correct 156 ms 40264 KB Output is correct
7 Correct 238 ms 45164 KB Output is correct
8 Correct 227 ms 53812 KB Output is correct
9 Correct 225 ms 54088 KB Output is correct
10 Correct 171 ms 52776 KB Output is correct
11 Correct 223 ms 54572 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 48184 KB Output is correct
2 Correct 1688 ms 208960 KB Output is correct
3 Correct 2525 ms 280104 KB Output is correct
4 Correct 519 ms 102824 KB Output is correct
5 Correct 2753 ms 355716 KB Output is correct
6 Correct 2292 ms 293708 KB Output is correct
7 Correct 537 ms 93772 KB Output is correct
8 Correct 242 ms 70584 KB Output is correct
9 Correct 607 ms 99664 KB Output is correct
10 Correct 520 ms 90964 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 48208 KB Output is correct
2 Correct 221 ms 53320 KB Output is correct
3 Correct 221 ms 53832 KB Output is correct
4 Correct 230 ms 58696 KB Output is correct
5 Correct 238 ms 52040 KB Output is correct
6 Correct 156 ms 40264 KB Output is correct
7 Correct 238 ms 45164 KB Output is correct
8 Correct 227 ms 53812 KB Output is correct
9 Correct 225 ms 54088 KB Output is correct
10 Correct 171 ms 52776 KB Output is correct
11 Correct 223 ms 54572 KB Output is correct
12 Correct 16 ms 48184 KB Output is correct
13 Correct 1688 ms 208960 KB Output is correct
14 Correct 2525 ms 280104 KB Output is correct
15 Correct 519 ms 102824 KB Output is correct
16 Correct 2753 ms 355716 KB Output is correct
17 Correct 2292 ms 293708 KB Output is correct
18 Correct 537 ms 93772 KB Output is correct
19 Correct 242 ms 70584 KB Output is correct
20 Correct 607 ms 99664 KB Output is correct
21 Correct 520 ms 90964 KB Output is correct
22 Correct 1713 ms 204844 KB Output is correct
23 Correct 1703 ms 214548 KB Output is correct
24 Correct 2671 ms 277312 KB Output is correct
25 Correct 2761 ms 286768 KB Output is correct
26 Correct 2554 ms 278604 KB Output is correct
27 Correct 3168 ms 349948 KB Output is correct
28 Correct 655 ms 102312 KB Output is correct
29 Correct 2598 ms 277748 KB Output is correct
30 Correct 2577 ms 278032 KB Output is correct
31 Correct 2586 ms 281028 KB Output is correct
32 Correct 670 ms 99656 KB Output is correct
33 Correct 264 ms 65208 KB Output is correct
34 Correct 408 ms 79916 KB Output is correct
35 Correct 423 ms 82444 KB Output is correct
36 Correct 513 ms 92744 KB Output is correct
37 Correct 492 ms 85792 KB Output is correct