oj.uz

답안 #240021

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
240021 2020-06-17T17:53:40 Z rajarshi_basu 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 97572 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
 
#include <stdio.h>     
#include <stdlib.h>    
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <deque>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#include "factories.h"
 
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long 
#define ld long double
#define vi vector<int>
#define pb push_back
#define ff first
#define ss second
#define il pair<int,ll>
#define ii pair<int,int>
#define lii pair<pair<ll,int>,il>
#define iii pair<int,ii>
#define iiii pair<iii,int>
#define pll pair<ll,ll>
#define plll pair<ll,pll>
#define vv vector
#define endl '\n'
 
using namespace std;
 
const ll INF = 1e17;
const int MAXN = 5e5+5;
const int LOGN = 20;
 
int n;
// ==================== Sparse table and basic graph setup ============================
vv<ii> g[MAXN];
ll dist[MAXN];
int depth[MAXN];
int ancestors[LOGN][MAXN];
void dfs_init_setup_lca(int node,int p = -1){
    ancestors[0][node] = p;
    for(auto e: g[node]){
        if(e.ff == p)continue;
        dist[e.ff] = e.ss + dist[node];
        depth[e.ff] = 1+ depth[node];
        dfs_init_setup_lca(e.ff,node);
    }
}
void calculateSparseTable(){
    FOR(i,LOGN){
        if(i > 0){
            FOR(j,n){
                int p = ancestors[i-1][j];
                if(p == -1)ancestors[i][j] = -1;
                else ancestors[i][j] = ancestors[i-1][p];
            }
        }
    }
}
int LCA(int a,int b){
    if(depth[a] < depth[b])swap(a,b);
    FOR(i,LOGN){
        int j = LOGN-i-1;
        if(depth[ancestors[j][a]] >= depth[b])a = ancestors[j][a];
    }
    if(a == b)return a;
    FOR(i,LOGN){
        int j = LOGN - i -1;
        if(ancestors[j][a] != ancestors[j][b])
            a = ancestors[j][a],
            b = ancestors[j][b];
    }
    return ancestors[0][a];
}
ll distance(int a,int b){
    return dist[a] + dist[b] - 2*dist[LCA(a,b)];
}
// ==================== Centroid tree construction ====================================
bool blocked[MAXN];
int subtree[MAXN];
int centroidParent[MAXN];
int ctr = 0;
void dfs_centroid_setup(int node,int p = -1){
    ctr++;
    subtree[node] = 1;
    for(auto e: g[node]){
        if(blocked[e.ff] or e.ff == p)continue;
        dfs_centroid_setup(e.ff,node);
        subtree[node] += subtree[e.ff];
    }
}
int getCentroid(int node,int tot,int p = -1){
    for(auto e: g[node]){
        if(blocked[e.ff] or e.ff == p)continue;
        if(2*subtree[e.ff] > tot)return getCentroid(e.ff,tot,node); 
    }
    return node;
}
queue<ii> subtrees_remaining;
void processCentroid(int node,int par){
    dfs_centroid_setup(node);
    int c = getCentroid(node,subtree[node]);
    centroidParent[c] = par;
    for(auto e: g[c]){
        if(blocked[e.ff])continue;
        subtrees_remaining.push({e.ff,c});
    }
    blocked[c] = 1;
}
 
void centroidDecomp(){
    subtrees_remaining.push({0,-1});
    while(!subtrees_remaining.empty()){
        auto e = subtrees_remaining.front();subtrees_remaining.pop();
        processCentroid(e.ff,e.ss);
    }
}
// ==================== Problem Specific Stuff =======================================
ll ans[MAXN];
 
 
void Init(int n, int A[], int B[], int D[]) {
    ::n = n;
    FOR(i,n-1){
        g[A[i]].pb({B[i],D[i]});
        g[B[i]].pb({A[i],D[i]});
    }
    dfs_init_setup_lca(0);
    calculateSparseTable();
    centroidDecomp();
    //cout << ctr << endl;
    FOR(i,n)ans[i] = INF;
}
 
long long Query(int S, int X[], int T, int Y[]) {
    vv<int> affectedNodes;
    //cout << "LCA: " << LCA(2,5) << " " << distance(2,5) << endl;
    FOR(i,S){
        int item = X[i];
        while(item != -1){
            affectedNodes.pb(item);
            ans[item] = min(ans[item],distance(item,X[i]));
            item = centroidParent[item];
        }
    }
    ll d = INF;
    FOR(i,T){
        int item = Y[i];
        while(item != -1){
            d = min(d,distance(item,Y[i])+ans[item]);
            item = centroidParent[item];
        }
    }
    for(auto e: affectedNodes)ans[e] = INF;
    return d;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 12672 KB Output is correct
2 Correct 2282 ms 21904 KB Output is correct
3 Correct 3917 ms 22300 KB Output is correct
4 Correct 3766 ms 22688 KB Output is correct
5 Correct 4519 ms 22552 KB Output is correct
6 Correct 963 ms 22084 KB Output is correct
7 Correct 3883 ms 22352 KB Output is correct
8 Correct 4054 ms 22008 KB Output is correct
9 Correct 4418 ms 22404 KB Output is correct
10 Correct 957 ms 22264 KB Output is correct
11 Correct 3905 ms 21924 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 12416 KB Output is correct
2 Execution timed out 8101 ms 97572 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 12672 KB Output is correct
2 Correct 2282 ms 21904 KB Output is correct
3 Correct 3917 ms 22300 KB Output is correct
4 Correct 3766 ms 22688 KB Output is correct
5 Correct 4519 ms 22552 KB Output is correct
6 Correct 963 ms 22084 KB Output is correct
7 Correct 3883 ms 22352 KB Output is correct
8 Correct 4054 ms 22008 KB Output is correct
9 Correct 4418 ms 22404 KB Output is correct
10 Correct 957 ms 22264 KB Output is correct
11 Correct 3905 ms 21924 KB Output is correct
12 Correct 18 ms 12416 KB Output is correct
13 Execution timed out 8101 ms 97572 KB Time limit exceeded
14 Halted 0 ms 0 KB -