oj.uz

Submission #536639

# Submission time Handle Problem Language Result Execution time Memory
536639 2022-03-13T16:12:24 Z michao Factories (JOI14_factories) C++14
100 / 100
 4118 ms 269076 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int MAX=5e5+5;
const ll inf=(ll)1e18+9;
const int STALA=20;
int A[MAX][STALA];
bool blocked[MAX];
int rwdc[MAX];
int sub[MAX];
vi PC[MAX];
vector<pii> P[MAX];
ll dist[MAX][STALA];
int ojciec[MAX];
int gle[MAX];
int n;
int dfs(int u,int fa){
  sub[u]=1;
  for (auto it:P[u]) if (it.st!=fa && !blocked[it.st]) sub[u]+=dfs(it.st,u);
  return sub[u];
}
 
int find_centroid(int u,int fa,int ile){
  for (auto it:P[u]) if (it.st!=fa && !blocked[it.st] && sub[it.st]>ile/2)return find_centroid(it.st,u,ile);
  return u;
}

void rozjebiesystem(int u,int fa,int grandpa){
	for (auto it:P[u]){
		int v=it.st;
		if (blocked[v] || v==fa)continue;
		dist[v][gle[grandpa]]=dist[u][gle[grandpa]]+it.nd;
		rozjebiesystem(v,u,grandpa);
	}
}

void centroid(int u,int fa){
  int roz=dfs(u,fa);
  int next_centroid=find_centroid(u,fa,roz);
  rwdc[next_centroid]=fa;
  gle[next_centroid]=gle[fa]+1;
  rozjebiesystem(next_centroid,-1,next_centroid);
  blocked[next_centroid]=true;
  for (auto it:P[next_centroid]){
    if (blocked[it.st])continue;
    centroid(it.st,next_centroid); 
  }
}
ll d1[MAX];
ll prepro[MAX][STALA];
void Init(int N,int A[],int B[],int D[]){
	n=N;
	for (int i=1;i<=n;i++){
		d1[i]=inf;
	}
	for (int i=0;i<n-1;i++){
		A[i]++;
		B[i]++;
		P[A[i]].pb(mp(B[i],D[i]));
		P[B[i]].pb(mp(A[i],D[i]));
	}
	centroid(1,-1);
	for (int i=1;i<=n;i++){
		for (int j=0;j<=gle[i];j++){
			prepro[i][j]=dist[i][gle[i]-j];
		}
	}
}

ll Query(int S,int X[],int T,int Y[]){
	ll ans=inf;
	for (int i=0;i<S;i++)X[i]++;
	for (int i=0;i<T;i++)Y[i]++;
	for (int i=0;i<S;i++){
		int u=X[i];
		int gle=0;
		while (u!=-1){
		//	cout<<"TERAZ "<<u<<" "<<X[i]<<" "<<distance(u,X[i])<<" "<<lca(u,X[i])<<"\n";
			d1[u]=min(d1[u],prepro[X[i]][gle]);
			u=rwdc[u];
			gle++;
		}
	}
	int ile=0;
	for (int i=0;i<T;i++){
		int u=Y[i];
		int gle=0;
		while (u!=-1){
			ans=min(ans,d1[u]+prepro[Y[i]][gle]);
			u=rwdc[u];
			gle++;
		}
	}
	
	for (int i=0;i<S;i++){
		int u=X[i];
		while (u!=-1){
		  d1[u]=inf;
		  //d2[u]=inf;
			u=rwdc[u];
		}
	}
	return ans;
}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:97:6: warning: unused variable 'ile' [-Wunused-variable]
   97 |  int ile=0;
      |      ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24276 KB Output is correct
2 Correct 254 ms 33740 KB Output is correct
3 Correct 326 ms 33644 KB Output is correct
4 Correct 281 ms 33764 KB Output is correct
5 Correct 314 ms 33916 KB Output is correct
6 Correct 194 ms 33720 KB Output is correct
7 Correct 291 ms 33696 KB Output is correct
8 Correct 287 ms 33804 KB Output is correct
9 Correct 298 ms 34036 KB Output is correct
10 Correct 215 ms 33664 KB Output is correct
11 Correct 268 ms 33752 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24020 KB Output is correct
2 Correct 1727 ms 222060 KB Output is correct
3 Correct 2714 ms 223660 KB Output is correct
4 Correct 589 ms 222944 KB Output is correct
5 Correct 3677 ms 246360 KB Output is correct
6 Correct 2765 ms 243724 KB Output is correct
7 Correct 805 ms 85792 KB Output is correct
8 Correct 390 ms 86544 KB Output is correct
9 Correct 946 ms 90016 KB Output is correct
10 Correct 829 ms 87124 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24276 KB Output is correct
2 Correct 254 ms 33740 KB Output is correct
3 Correct 326 ms 33644 KB Output is correct
4 Correct 281 ms 33764 KB Output is correct
5 Correct 314 ms 33916 KB Output is correct
6 Correct 194 ms 33720 KB Output is correct
7 Correct 291 ms 33696 KB Output is correct
8 Correct 287 ms 33804 KB Output is correct
9 Correct 298 ms 34036 KB Output is correct
10 Correct 215 ms 33664 KB Output is correct
11 Correct 268 ms 33752 KB Output is correct
12 Correct 15 ms 24020 KB Output is correct
13 Correct 1727 ms 222060 KB Output is correct
14 Correct 2714 ms 223660 KB Output is correct
15 Correct 589 ms 222944 KB Output is correct
16 Correct 3677 ms 246360 KB Output is correct
17 Correct 2765 ms 243724 KB Output is correct
18 Correct 805 ms 85792 KB Output is correct
19 Correct 390 ms 86544 KB Output is correct
20 Correct 946 ms 90016 KB Output is correct
21 Correct 829 ms 87124 KB Output is correct
22 Correct 2001 ms 247932 KB Output is correct
23 Correct 2087 ms 250736 KB Output is correct
24 Correct 3231 ms 249856 KB Output is correct
25 Correct 3279 ms 253684 KB Output is correct
26 Correct 3240 ms 249844 KB Output is correct
27 Correct 4118 ms 269076 KB Output is correct
28 Correct 938 ms 251588 KB Output is correct
29 Correct 3558 ms 249724 KB Output is correct
30 Correct 3522 ms 249220 KB Output is correct
31 Correct 3139 ms 249740 KB Output is correct
32 Correct 871 ms 90552 KB Output is correct
33 Correct 357 ms 86980 KB Output is correct
34 Correct 563 ms 83500 KB Output is correct
35 Correct 567 ms 83600 KB Output is correct
36 Correct 754 ms 84052 KB Output is correct
37 Correct 751 ms 84060 KB Output is correct