oj.uz

Submission #656965

# Submission time Handle Problem Language Result Execution time Memory
656965 2022-11-08T14:45:09 Z anhduc2701 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 402196 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;
    killed[c]=1;
    dfs2(c, p, c, 0);
    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 34 ms 36172 KB Output is correct
2 Correct 1390 ms 46560 KB Output is correct
3 Correct 2090 ms 47548 KB Output is correct
4 Correct 2037 ms 47420 KB Output is correct
5 Correct 2510 ms 48208 KB Output is correct
6 Correct 429 ms 45060 KB Output is correct
7 Correct 2080 ms 47744 KB Output is correct
8 Correct 2136 ms 47656 KB Output is correct
9 Correct 2495 ms 48264 KB Output is correct
10 Correct 417 ms 45084 KB Output is correct
11 Correct 2060 ms 47444 KB Output is correct

Subtask #2
0 / 18.0

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

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 36172 KB Output is correct
2 Correct 1390 ms 46560 KB Output is correct
3 Correct 2090 ms 47548 KB Output is correct
4 Correct 2037 ms 47420 KB Output is correct
5 Correct 2510 ms 48208 KB Output is correct
6 Correct 429 ms 45060 KB Output is correct
7 Correct 2080 ms 47744 KB Output is correct
8 Correct 2136 ms 47656 KB Output is correct
9 Correct 2495 ms 48264 KB Output is correct
10 Correct 417 ms 45084 KB Output is correct
11 Correct 2060 ms 47444 KB Output is correct
12 Correct 20 ms 35796 KB Output is correct
13 Execution timed out 8087 ms 402196 KB Time limit exceeded
14 Halted 0 ms 0 KB -