oj.uz

Submission #825273

# Submission time Handle Problem Language Result Execution time Memory
825273 2023-08-14T16:33:42 Z KLPP Factories (JOI14_factories) C++14
100 / 100
 5925 ms 400768 KB 
#include "factories.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)

void DFS(int node, vector<vector<pair<int,lld> > >&nei, vector<int> &sz, vector<bool> &used){
	sz[node]=1;
	trav(a,nei[node]){
		if(sz[a.first]==-1 && !used[a.first]){
			DFS(a.first,nei,sz,used);
			sz[node]+=sz[a.first];
		}
	}
}
int findcentroid(int node, int tree_sz, vector<vector<pair<int,lld> > >&nei, vector<int> &sz, vector<bool> &used){
	trav(a,nei[node]){
		if(!used[a.first] && 2*sz[a.first]>tree_sz && sz[a.first]<sz[node]){
			return findcentroid(a.first,tree_sz,nei,sz,used);
		}
	}
	return node;
}
void DFS2(int node, lld dist, int cent, vector<vector<pair<int,lld> > >&nei,vector<bool> &visited, vector<bool> &used,vector<vector<pair<int,lld> > > &dists){
	dists[node].push_back({cent,dist});
	visited[node]=true;
	trav(a,nei[node]){
		if(!visited[a.first] && !used[a.first]){
			DFS2(a.first,dist+a.second,cent,nei,visited,used,dists);
		}
	}
}
const lld INF=1e18;
int n;
vector<vector<pair<int,lld>> >dists;
vector<lld> ans;
void Init(int N, int A[], int B[], int D[]) {
	n=N;
	ans.resize(n,INF);
	vector<vector<pair<int,lld>> >nei(n);
	rep(i,0,n-1){
		int x,y;
		lld z;
		x=A[i];
		y=B[i];
		z=D[i];
		nei[x].push_back({y,z});
		nei[y].push_back({x,z});
	}
	dists.resize(n);
	vector<int> sz;
	vector<bool> used(n,false);
	vector<bool> visited;
	rep(t,0,25){
		sz.clear();
		sz.resize(n,-1);
		visited.clear();
		visited.resize(n,false);
		rep(i,0,n){
			if(!used[i] && sz[i]==-1){
				DFS(i,nei,sz,used);
				int cent=findcentroid(i,sz[i],nei,sz,used);
				DFS2(cent,0,cent,nei,visited,used,dists);
				used[cent]=true;
			}
		}
	}
}
queue<int> q;

long long Query(int S, int X[], int T, int Y[]) {
  int s,t;
	s=S;
	t=T;
		rep(i,0,s){
			int x;
			x=X[i];
			trav(a,dists[x]){
				q.push(a.first);
				ans[a.first]=min(ans[a.first],a.second);
			}
		}
		lld finans=INF;
		rep(i,0,t){
			int x;
			x=Y[i];
			trav(a,dists[x]){
				finans=min(finans,a.second+ans[a.first]);
			}
		}
		while(!q.empty()){
			int u=q.front();
			q.pop();
			ans[u]=INF;
		}
		return finans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 980 KB Output is correct
2 Correct 216 ms 19168 KB Output is correct
3 Correct 283 ms 19620 KB Output is correct
4 Correct 258 ms 19632 KB Output is correct
5 Correct 283 ms 20028 KB Output is correct
6 Correct 185 ms 18480 KB Output is correct
7 Correct 291 ms 19640 KB Output is correct
8 Correct 222 ms 19656 KB Output is correct
9 Correct 295 ms 20016 KB Output is correct
10 Correct 189 ms 18548 KB Output is correct
11 Correct 276 ms 19628 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 540 KB Output is correct
2 Correct 3375 ms 217476 KB Output is correct
3 Correct 5063 ms 303876 KB Output is correct
4 Correct 915 ms 110496 KB Output is correct
5 Correct 5925 ms 391384 KB Output is correct
6 Correct 5207 ms 303948 KB Output is correct
7 Correct 1208 ms 63428 KB Output is correct
8 Correct 377 ms 40240 KB Output is correct
9 Correct 1267 ms 82664 KB Output is correct
10 Correct 1110 ms 63992 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 980 KB Output is correct
2 Correct 216 ms 19168 KB Output is correct
3 Correct 283 ms 19620 KB Output is correct
4 Correct 258 ms 19632 KB Output is correct
5 Correct 283 ms 20028 KB Output is correct
6 Correct 185 ms 18480 KB Output is correct
7 Correct 291 ms 19640 KB Output is correct
8 Correct 222 ms 19656 KB Output is correct
9 Correct 295 ms 20016 KB Output is correct
10 Correct 189 ms 18548 KB Output is correct
11 Correct 276 ms 19628 KB Output is correct
12 Correct 2 ms 540 KB Output is correct
13 Correct 3375 ms 217476 KB Output is correct
14 Correct 5063 ms 303876 KB Output is correct
15 Correct 915 ms 110496 KB Output is correct
16 Correct 5925 ms 391384 KB Output is correct
17 Correct 5207 ms 303948 KB Output is correct
18 Correct 1208 ms 63428 KB Output is correct
19 Correct 377 ms 40240 KB Output is correct
20 Correct 1267 ms 82664 KB Output is correct
21 Correct 1110 ms 63992 KB Output is correct
22 Correct 3321 ms 224332 KB Output is correct
23 Correct 3148 ms 226832 KB Output is correct
24 Correct 4768 ms 312420 KB Output is correct
25 Correct 4716 ms 314076 KB Output is correct
26 Correct 4675 ms 313412 KB Output is correct
27 Correct 5490 ms 400768 KB Output is correct
28 Correct 872 ms 120452 KB Output is correct
29 Correct 4777 ms 312784 KB Output is correct
30 Correct 4605 ms 313108 KB Output is correct
31 Correct 4565 ms 313072 KB Output is correct
32 Correct 1071 ms 82644 KB Output is correct
33 Correct 279 ms 40184 KB Output is correct
34 Correct 583 ms 57816 KB Output is correct
35 Correct 639 ms 58568 KB Output is correct
36 Correct 836 ms 62840 KB Output is correct
37 Correct 793 ms 62784 KB Output is correct