oj.uz

답안 #709523

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
709523 2023-03-13T20:36:50 Z Ahmed57 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 206676 KB 
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>

using namespace std;
vector<pair<int,long long>> adj[500001];
int hi[500001];
int P[500001][19];
long long sum[500001][19];
void dfs(int i,int pr,long long len){
    hi[i] = hi[pr]+1;
    P[i][0]= pr;
    sum[i][0] =len;
    for(int j = 1;j<19;j++){
        P[i][j] = P[P[i][j-1]][j-1];
        sum[i][j]= sum[i][j-1]+sum[P[i][j-1]][j-1];
    }
    for(auto j:adj[i]){
        if(j.first!=pr){
            dfs(j.first,i,j.second);
        }
    }
}long long lca(int x,int y){
    long long su = 0;
    if(hi[x]<hi[y]) swap(x,y);
    for(int k=18;k>=0;k--)
    {
        if(hi[x]-(1<<k) >= hi[y]){
            su+=sum[x][k];
            x=P[x][k];
        }
    }
    if(x==y) return su;
    for(int k=18;k>=0;k--)
    {
        if(P[x][k] != P[y][k]){
            su+=sum[x][k]+sum[y][k];
            x=P[x][k],y=P[y][k];
        }
    }
    return su+sum[x][0]+sum[y][0];
}
int sz[500001];
int vis[500001];
int par[500001];
long long best[500001];
int vi[500001];
int va = 1;
void upd(int i){
    long long s = i;
    while(s!=-1){
        if(vi[s]!=va){
            vi[s] =va;
            best[s] = 1e18;
        }
        best[s] = min(best[s],lca(i,s));
        s= par[s];
    }
}
long long ans(int i){
    long long s = i , re = 1e18;
    while(s!=-1){
        if(vi[s]!=va){
            vi[s] =va;
            best[s] = 1e18;
        }
        re = min(re,best[s]+lca(i,s));
        s= par[s];
    }
    return re;
}
int find_size(int v, int p = -1) {
    if(vis[v]) return 0;
    sz[v] = 1;
    for(auto x: adj[v]) {
        if (x.first != p) {
            sz[v] += find_size(x.first, v);
        }
    }
    return sz[v];
}
int find_centroid(int v, int p, int n) {
    for (auto x: adj[v]) {
        if (x.first != p) {
            if (!vis[x.first] && sz[x.first] > n / 2) {
                return find_centroid(x.first, v, n);
            }
        }
    }
    return v;
}
void centroid(int v = 0, int p = -1) {
    find_size(v);
    int c = find_centroid(v,-1,sz[v]);
    vis[c] = true;
    par[c] = p;
    for(auto x:adj[c]) {
        if (!vis[x.first]) {
            centroid(x.first, c);
        }
    }
}
void Init(int N,int A[],int B[],int D[]){
    for(int i = 0;i<N-1;i++){
        adj[A[i]].push_back({B[i],D[i]});
        adj[B[i]].push_back({A[i],D[i]});
    }
    centroid();
    dfs(0,0,0);
}
long long Query(int S, int X[], int T,int Y[]) {
	for(int i = 0;i<S;i++){
        upd(X[i]);
	}
	long long Res = 1e18;
	for(int i = 0;i<T;i++){
        Res = min(Res,ans(Y[i]));
	}
	va++;
	return Res;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 12628 KB Output is correct
2 Correct 713 ms 25192 KB Output is correct
3 Correct 1494 ms 25336 KB Output is correct
4 Correct 1495 ms 25332 KB Output is correct
5 Correct 1862 ms 25524 KB Output is correct
6 Correct 294 ms 25188 KB Output is correct
7 Correct 1569 ms 25288 KB Output is correct
8 Correct 1580 ms 25340 KB Output is correct
9 Correct 1808 ms 25604 KB Output is correct
10 Correct 260 ms 25212 KB Output is correct
11 Correct 1439 ms 25336 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 12372 KB Output is correct
2 Correct 2536 ms 177152 KB Output is correct
3 Correct 6787 ms 180088 KB Output is correct
4 Correct 816 ms 183052 KB Output is correct
5 Execution timed out 8021 ms 206676 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 12628 KB Output is correct
2 Correct 713 ms 25192 KB Output is correct
3 Correct 1494 ms 25336 KB Output is correct
4 Correct 1495 ms 25332 KB Output is correct
5 Correct 1862 ms 25524 KB Output is correct
6 Correct 294 ms 25188 KB Output is correct
7 Correct 1569 ms 25288 KB Output is correct
8 Correct 1580 ms 25340 KB Output is correct
9 Correct 1808 ms 25604 KB Output is correct
10 Correct 260 ms 25212 KB Output is correct
11 Correct 1439 ms 25336 KB Output is correct
12 Correct 9 ms 12372 KB Output is correct
13 Correct 2536 ms 177152 KB Output is correct
14 Correct 6787 ms 180088 KB Output is correct
15 Correct 816 ms 183052 KB Output is correct
16 Execution timed out 8021 ms 206676 KB Time limit exceeded
17 Halted 0 ms 0 KB -