oj.uz

Submission #959512

# Submission time Handle Problem Language Result Execution time Memory
959512 2024-04-08T11:10:50 Z dong_gas Factories (JOI14_factories) C++17
15 / 100
 8000 ms 146016 KB 
#include <bits/extc++.h>
#include "factories.h"
#define all(v) v.begin(), v.end()
#define zip(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int n, q;
int sz[500050], use[500050], cent_papa[500050], papa[500050][23], dep[500050];
ll dp[500050];
vector<pint> adj[500050];
ll m[500050];

void dfs(int u, int p=0) {
    papa[u][0]=p;
    dep[u]=dep[p]+1;
    for(auto& [v, w]: adj[u]) {
        if(v==p) continue;
        dp[v]=dp[u]+w;
        dfs(v,u);
    }
}

int lca(int u, int v) {
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=22;i>=0;i--) if(dep[u]-dep[v]>=(1<<i)) u=papa[u][i];
    if(u==v) return u;
    for(int i=22;i>=0;i--) if(papa[u][i] ^ papa[v][i]) u=papa[u][i], v=papa[v][i];
    return papa[u][0];
}

ll get_dist(int u, int v) { return dp[u]+dp[v]-2*dp[lca(u,v)]; }

int get_size(int u, int p=0) {
    sz[u]=1;
    for(auto& [v, w]:adj[u]) {
        if(use[v] || p==v) continue;
        sz[u]+=get_size(v,u);
    }
    return sz[u];
}

int get_cent(int u, int p, int cnt) {
    for(auto& [v, w]:adj[u]) {
        if(use[v] || v==p) continue;
        if(sz[v]>cnt/2) return get_cent(v,u,cnt);
    }
    return u;
}

void dnc(int u, int p=0) {//p는 이전 cent
    int cent=get_cent(u,p,get_size(u,p));
    cent_papa[cent]=p;
    use[cent]=1;
    for(auto& [v, w]:adj[cent]) if(!use[v]) dnc(v,cent);
}

void update(int u) {
    int now=u;
    do {
        ll dist=get_dist(now,u);
        m[now]=min(m[now],dist);
        now=cent_papa[now];
    } while(now!=0);    
}

void downdate(int u) {
    int now=u;
    do {
        ll dist=get_dist(now,u);
        m[now]=1e18;
        now=cent_papa[now];
    } while(now!=0);    
}

ll query(int u) {
    int now=u;
    ll ret=1e18;
    do {        
        ret=min(ret, get_dist(u,now) + m[now]);
        now=cent_papa[now];        
    } while(now!=0);
    return (ret<1e18) ? ret : -1;
}

void Init(int N, int A[], int B[], int D[]) {
    n=N;
    for(int i=0;i<n-1;i++) {
        adj[A[i]+1].emplace_back(B[i]+1,D[i]);
        adj[B[i]+1].emplace_back(A[i]+1,D[i]);
    }
    dfs(1), dnc(1);
    fill(m+1,m+n+1,1e18);
    for(int j=1;j<23;j++) for(int i=1;i<=n;i++) papa[i][j]=papa[papa[i][j-1]][j-1];
}

long long Query(int S, int X[], int T, int Y[]) {
    ll ret=1e18;
    for(int i=0;i<S;i++) update(X[i]+1);
    for(int i=0;i<T;i++) ret=min(ret,query(Y[i]+1));
    for(int i=0;i<S;i++) downdate(X[i]+1);
    return ret;
}

Compilation message

factories.cpp: In function 'void downdate(int)':
factories.cpp:74:12: warning: unused variable 'dist' [-Wunused-variable]
   74 |         ll dist=get_dist(now,u);
      |            ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 14424 KB Output is correct
2 Correct 629 ms 32140 KB Output is correct
3 Correct 1415 ms 32420 KB Output is correct
4 Correct 1372 ms 32380 KB Output is correct
5 Correct 1728 ms 32416 KB Output is correct
6 Correct 230 ms 31988 KB Output is correct
7 Correct 1389 ms 32192 KB Output is correct
8 Correct 1468 ms 32336 KB Output is correct
9 Correct 1744 ms 32376 KB Output is correct
10 Correct 237 ms 32204 KB Output is correct
11 Correct 1386 ms 32008 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14204 KB Output is correct
2 Correct 2171 ms 123000 KB Output is correct
3 Correct 5615 ms 123612 KB Output is correct
4 Correct 731 ms 123232 KB Output is correct
5 Execution timed out 8103 ms 146016 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 14424 KB Output is correct
2 Correct 629 ms 32140 KB Output is correct
3 Correct 1415 ms 32420 KB Output is correct
4 Correct 1372 ms 32380 KB Output is correct
5 Correct 1728 ms 32416 KB Output is correct
6 Correct 230 ms 31988 KB Output is correct
7 Correct 1389 ms 32192 KB Output is correct
8 Correct 1468 ms 32336 KB Output is correct
9 Correct 1744 ms 32376 KB Output is correct
10 Correct 237 ms 32204 KB Output is correct
11 Correct 1386 ms 32008 KB Output is correct
12 Correct 9 ms 14204 KB Output is correct
13 Correct 2171 ms 123000 KB Output is correct
14 Correct 5615 ms 123612 KB Output is correct
15 Correct 731 ms 123232 KB Output is correct
16 Execution timed out 8103 ms 146016 KB Time limit exceeded
17 Halted 0 ms 0 KB -