oj.uz

Submission #656892

# Submission time Handle Problem Language Result Execution time Memory
656892 2022-11-08T13:07:29 Z anhduc2701 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 398412 KB 
#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll;
const ll INF=1e18;
const int maxn=1e6+5;
const int mod=1e9+7;
const int mo=998244353;
using pi=pair<ll,ll>;
using vi=vector<ll>;
using pii=pair<pair<ll,ll>,ll>;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI 3.14159265359
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
set<pair<int,int>>G[500005];
int sz[500005];
int pa[500005];
map<int,long long>dis[500005];
long long ans[500005];
int dfsz(int u, int p) {
    sz[u] = 1;
    for(auto v : G[u]) if(v.first != p) {
      sz[u] += dfsz(v.first, u);
    }
    return sz[u];
}
int centroid(int u, int p, int n) {
    for(auto v : G[u]) if(v.first != p) {
        if(sz[v.first] > n / 2) return centroid(v.first, u, n);
    }
    return u;
  }
void dfs2(int u, int p, int c, long long d) {
    dis[c][u] = d;
    for(auto v : G[u]) if(v.first != p) {
        dfs2(v.first, u, c, d + (long long)v.second);
    }
}
void build(int u, int p) {
    int n1 = dfsz(u, p);
    int c = centroid(u, p, n1);
    if(p == -1) p = c;
    pa[c] = p;
    dfs2(c, p, c, 0);
    vector<pair<int,int>> tmp(G[c].begin(), G[c].end());
    for(auto v : tmp) {
        G[c].erase({v.first,v.second});
        G[v.first].erase({c,v.second});
        build(v.first, c);
    }
}
void upd(int u){
    int v=u;
    while(v!=0){
        ans[v]=min(ans[v],dis[v][u]);
        v=pa[v];
    }
}
void upd1(int u){
    int v=u;
    while(v!=0){
        ans[v]=INF;
        v=pa[v];
    }
}
long long query(int u) {
    long long mi = INF;
    int v=u;
     while(v!=0){
        mi=min(ans[v]+dis[v][u],mi);
        v=pa[v];
    }
    return mi;
}
void Init(int N,int A[],int B[],int D[]){
	n=N;
	for(int i=0;i<N-1;i++){
		G[A[i]+1].insert({B[i]+1,D[i]});
		G[B[i]+1].insert({A[i]+1,D[i]});
	}
	build(1,0);
	for(int i=1;i<=n;i++){
        ans[i]=INF;
	}
}
long long Query(int S,int X[],int T,int Y[]){
	for(int i=0;i<S;i++){
		upd(X[i]+1);
	}
	long long an=INF;
	for(int i=0;i<T;i++){
		an=min(an,query(Y[i]+1));
	}
	for(int i=0;i<S;i++){
        upd1(X[i]+1);
	}
	return an;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 47700 KB Output is correct
2 Correct 1448 ms 65212 KB Output is correct
3 Correct 2163 ms 62724 KB Output is correct
4 Correct 2154 ms 62712 KB Output is correct
5 Correct 2573 ms 61884 KB Output is correct
6 Correct 424 ms 58704 KB Output is correct
7 Correct 2072 ms 60876 KB Output is correct
8 Correct 2224 ms 61052 KB Output is correct
9 Correct 2677 ms 61820 KB Output is correct
10 Correct 423 ms 58768 KB Output is correct
11 Correct 2128 ms 60988 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47712 KB Output is correct
2 Execution timed out 8082 ms 398412 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 47700 KB Output is correct
2 Correct 1448 ms 65212 KB Output is correct
3 Correct 2163 ms 62724 KB Output is correct
4 Correct 2154 ms 62712 KB Output is correct
5 Correct 2573 ms 61884 KB Output is correct
6 Correct 424 ms 58704 KB Output is correct
7 Correct 2072 ms 60876 KB Output is correct
8 Correct 2224 ms 61052 KB Output is correct
9 Correct 2677 ms 61820 KB Output is correct
10 Correct 423 ms 58768 KB Output is correct
11 Correct 2128 ms 60988 KB Output is correct
12 Correct 29 ms 47712 KB Output is correct
13 Execution timed out 8082 ms 398412 KB Time limit exceeded
14 Halted 0 ms 0 KB -