oj.uz

Submission #780137

# Submission time Handle Problem Language Result Execution time Memory
780137 2023-07-12T06:54:16 Z CESxRhino Factories (JOI14_factories) C++14
100 / 100
 2981 ms 175472 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define ii pair<int,int>
#define f first
#define s second
#define pb push_back
#define ll long long
#define endl '\n'
using namespace std;
vector<ii> w[500005];
vector<pair<int,ll> > w2[500005];
int level[500005][33];
int First[500005];
int End[500005];
ll dist[500005];
int x = __lg(500005) + 2;
int DFStime;
int color[500005];
int s[500005];
int t[500005];
ll mindist;
void DFS(int u,int par)
{
	First[u] = ++DFStime;
	level[u][0] = par;
	for(int i = 1;i < x;i++)
	{
		level[u][i] = level[level[u][i - 1]][i - 1];
	}
	for(auto v:w[u])
	{
		if(v.first != par)
		{
			dist[v.first] = dist[u] + v.second;
			DFS(v.first,u);
		}
	}
	End[u] = DFStime;
}
bool check(int u,int v)
{
	return (First[u] <= First[v] and End[v] <= End[u]);
}
int LCA(int u,int v)
{
	if(check(u,v))
	{
		return u;
	}
	if(check(v,u))
	{
		return v;
	}
	for(int i = 32;i >= 0;i--)
	{
		if(!check(level[u][i],v))
		{
			u = level[u][i];
		}
	}
	return level[u][0];
}
void Init(int n, int a[], int b[], int d[])
{
    for(int i = 0;i < n - 1;i++)
    {
        w[a[i]].pb({b[i],d[i]}),
        w[b[i]].pb({a[i],d[i]});	
	}
    DFS(0,0);
}
void edge(int u,int v)
{
	if(u == v)
	{
		return;
	}
	ll d = abs(dist[u] - dist[v]);
	w2[u].push_back({v,d});
	w2[v].push_back({u,d});
}
int virtual_tree(vector<int> &nodes)
{
	sort(nodes.begin(),nodes.end(),[](int &i, int &j){return (First[i] < First[j]);});
	for(int i = (int) (nodes.size()) - 2;i >= 0;i--)
	{
		int res = LCA(nodes[i],nodes[i + 1]);
		nodes.push_back(res);
	}
	sort(nodes.begin(),nodes.end(),[](int &i, int &j){return (First[i] < First[j]);});
	vector<int> s;
	s.push_back(nodes[0]);
	for(int i = 1;i < nodes.size();i++)
	{
		while(!check(s.back(),nodes[i]))
		{	
			edge(s.back(),s[s.size() - 2]);
			s.pop_back();
		}
		s.push_back(nodes[i]);
	}
	while(s.size() > 1)
	{
		edge(s.back(),s[s.size() - 2]);
		s.pop_back();
	}
	return s[0];
}
pair<ll,ll> DFS2(int u,int par)
{
	ll min1 = 1e18;
	ll min2 = 1e18;
	if(color[u] == 1)
	{
		min1 = 0;
	}
	else if(color[u] == 2)
	{
		min2 = 0;
	}
	for(auto v:w2[u])
	{
		if(v.first != par)
		{
			pair<ll,ll> tree = DFS2(v.first,u);
			min1 = min(min1,v.second + tree.first);
			min2 = min(min2,v.second + tree.second);
		}
	}
	mindist = min(mindist,min1 + min2);
	return {min1,min2};
}
long long Query(int n, int x[], int m, int y[])
{
	vector<int> nodes;
	for(int i = 0;i < n;i++)
	{
		nodes.push_back(x[i]);
		color[x[i]] = 1;
	}
	for(int i = 0;i < m;i++)
	{
		nodes.push_back(y[i]);
		color[y[i]] = 2;
	}
	int r = virtual_tree(nodes);
	mindist = 1e18;
	DFS2(r,r);
	for(auto x:nodes)
        w2[x].clear(),
        color[x] = 0;
	return mindist;
}

Compilation message

factories.cpp: In function 'int virtual_tree(std::vector<int>&)':
factories.cpp:93:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for(int i = 1;i < nodes.size();i++)
      |                ~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24148 KB Output is correct
2 Correct 759 ms 33064 KB Output is correct
3 Correct 743 ms 33180 KB Output is correct
4 Correct 717 ms 33240 KB Output is correct
5 Correct 507 ms 33308 KB Output is correct
6 Correct 672 ms 33020 KB Output is correct
7 Correct 766 ms 33168 KB Output is correct
8 Correct 712 ms 33380 KB Output is correct
9 Correct 512 ms 33304 KB Output is correct
10 Correct 662 ms 33008 KB Output is correct
11 Correct 742 ms 33040 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24020 KB Output is correct
2 Correct 1308 ms 143728 KB Output is correct
3 Correct 1957 ms 146612 KB Output is correct
4 Correct 1068 ms 144196 KB Output is correct
5 Correct 1251 ms 174100 KB Output is correct
6 Correct 2054 ms 148216 KB Output is correct
7 Correct 1687 ms 57200 KB Output is correct
8 Correct 1116 ms 57208 KB Output is correct
9 Correct 645 ms 61640 KB Output is correct
10 Correct 1603 ms 58316 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24148 KB Output is correct
2 Correct 759 ms 33064 KB Output is correct
3 Correct 743 ms 33180 KB Output is correct
4 Correct 717 ms 33240 KB Output is correct
5 Correct 507 ms 33308 KB Output is correct
6 Correct 672 ms 33020 KB Output is correct
7 Correct 766 ms 33168 KB Output is correct
8 Correct 712 ms 33380 KB Output is correct
9 Correct 512 ms 33304 KB Output is correct
10 Correct 662 ms 33008 KB Output is correct
11 Correct 742 ms 33040 KB Output is correct
12 Correct 13 ms 24020 KB Output is correct
13 Correct 1308 ms 143728 KB Output is correct
14 Correct 1957 ms 146612 KB Output is correct
15 Correct 1068 ms 144196 KB Output is correct
16 Correct 1251 ms 174100 KB Output is correct
17 Correct 2054 ms 148216 KB Output is correct
18 Correct 1687 ms 57200 KB Output is correct
19 Correct 1116 ms 57208 KB Output is correct
20 Correct 645 ms 61640 KB Output is correct
21 Correct 1603 ms 58316 KB Output is correct
22 Correct 2559 ms 154276 KB Output is correct
23 Correct 2288 ms 154544 KB Output is correct
24 Correct 2816 ms 157984 KB Output is correct
25 Correct 2882 ms 160568 KB Output is correct
26 Correct 2981 ms 152160 KB Output is correct
27 Correct 1966 ms 175472 KB Output is correct
28 Correct 1693 ms 152104 KB Output is correct
29 Correct 2974 ms 151076 KB Output is correct
30 Correct 2877 ms 150372 KB Output is correct
31 Correct 2872 ms 150928 KB Output is correct
32 Correct 858 ms 63572 KB Output is correct
33 Correct 1048 ms 60756 KB Output is correct
34 Correct 1314 ms 56444 KB Output is correct
35 Correct 1278 ms 56348 KB Output is correct
36 Correct 1431 ms 56916 KB Output is correct
37 Correct 1457 ms 56916 KB Output is correct