oj.uz

Submission #656958

# Submission time Handle Problem Language Result Execution time Memory
656958 2022-11-08T14:34:19 Z anhduc2701 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 402500 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;
vector<pair<int,int>>G[500005];
int sz[500005];
int pa[500005];
map<int,long long>dis[500005];
long long ans[500005];
int killed[500005];
int dfsz(int u, int p) {
    sz[u] = 1;
    for(auto v : G[u]) if(v.first != p && killed[v.first]==0) {
      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 && killed[v.first]==0) {
        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 && killed[v.first]==0) {
        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);
    killed[c]=1;
    for(auto v : G[c]) {
       	if(killed[v.first]==0){
        	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].pb({B[i]+1,D[i]});
		G[B[i]+1].pb({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;
}
/*
signed main(){

	int q;
	cin>>n>>q;
	for(int i=1;i<=n-1;i++){
		int x,y,d;
		cin>>x>>y>>d;
		x++;
		y++;
		G[x].push_back({y,d});
		G[y].push_back({x,d});
	}
	build(1,0);
	for(int j=1;j<=q;j++){
		int S,T;
		cin>>S>>T;
		for(int i=1;i<=n;i++){
			ans[i]=INF;
		}
		for(int i=0;i<S;i++){
			int x;
			cin>>x;
			upd(x+1);
		}
		long long an=INF;
		for(int i=0;i<T;i++){
			int y;
			cin>>y;
			an=min(an,query(y+1));

		}
		cout<<an<<"\n";
	}
}
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 36220 KB Output is correct
2 Correct 1478 ms 47144 KB Output is correct
3 Correct 2132 ms 48296 KB Output is correct
4 Correct 2173 ms 48024 KB Output is correct
5 Correct 2677 ms 48780 KB Output is correct
6 Correct 425 ms 45716 KB Output is correct
7 Correct 2169 ms 48152 KB Output is correct
8 Correct 2410 ms 48152 KB Output is correct
9 Correct 2663 ms 48908 KB Output is correct
10 Correct 428 ms 45760 KB Output is correct
11 Correct 2180 ms 48240 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 35796 KB Output is correct
2 Execution timed out 8106 ms 402500 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 36220 KB Output is correct
2 Correct 1478 ms 47144 KB Output is correct
3 Correct 2132 ms 48296 KB Output is correct
4 Correct 2173 ms 48024 KB Output is correct
5 Correct 2677 ms 48780 KB Output is correct
6 Correct 425 ms 45716 KB Output is correct
7 Correct 2169 ms 48152 KB Output is correct
8 Correct 2410 ms 48152 KB Output is correct
9 Correct 2663 ms 48908 KB Output is correct
10 Correct 428 ms 45760 KB Output is correct
11 Correct 2180 ms 48240 KB Output is correct
12 Correct 21 ms 35796 KB Output is correct
13 Execution timed out 8106 ms 402500 KB Time limit exceeded
14 Halted 0 ms 0 KB -