oj.uz

Submission #249355

# Submission time Handle Problem Language Result Execution time Memory
249355 2020-07-14T16:37:30 Z vanic ČVENK (COI15_cvenk) C++14
100 / 100
 777 ms 93048 KB 
#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <assert.h>

using namespace std;

const int maxn=1e5+5, maxm=2e6;
const int inf=30;
typedef long long ll;

int n;
pair < int, int > turist[maxn];
vector < pair < int, int > > put[maxn];
vector < pair < int, int > > ms[maxm];
int vrij[maxm];
int pod[maxm];

void resi(int ind, int x, int y, int pos1, int pos2){
	if(x==0 && y==0){
		return;
	}
	put[ind].push_back({x, y});
	if(x){
		while((x&(1<<pos1))==0){
			pos1++;
		}
	}
	else{
		pos1=inf;
	}
	if(y){
		while((y&(1<<pos2))==0){
			pos2++;
		}
	}
	else{
		pos2=inf;
	}
	if(pos1<pos2){
		resi(ind, x-x%(1<<pos2), y, pos1, pos2);
	}
	else if(pos1>pos2){
		resi(ind, x, y-y%(1<<pos1), pos1, pos2);
	}
	else{
		assert(0);
	}
}

int br;

bool cmp(vector < pair < int, int > > a, vector < pair < int, int > > b){
	if(b.empty()){
		return 0;
	}
	if(a.empty()){
		return 1;
	}
	if(a.back().first!=b.back().first){
		return a.back().first<b.back().first;
	}
	return a.back().second<b.back().second;
}

int dist(pair < int, int > a, pair < int, int > b){
	return abs(a.first-b.first)+abs(a.second-b.second);
}

void napravi(int na, pair < int, int > val, int poc, int kraj){
//	cout << "radim " << poc << " " << kraj << endl;
	sort(put+poc, put+kraj, cmp);
	int pos=poc;
	while(pos<kraj && put[pos].empty()){
		vrij[br]++;
		pos++;
	}
	pair < int, int > p;
	int prij=pos;
	int na1=na;
	pair < int, int > val1=val;
	while(pos<kraj){
		p=put[pos].back();
		br++;
//		cout << "spajam " << na1 << " " << br << endl;
		ms[na1].push_back({br, dist(val1, p)});
		ms[br].push_back({na1, dist(val1, p)});
		while(pos<kraj && put[pos].back()==p){
			put[pos].pop_back();
			pos++;
		}
		na1=br;
		napravi(br, p, prij, pos);
		prij=pos;
		val1=p;
	}
//	cout << "kraj---" << endl;
}

int dfs(int x, int prosl){
	pod[x]=vrij[x];
	for(int i=0; i<ms[x].size(); i++){
		if(ms[x][i].first!=prosl){
			pod[x]+=dfs(ms[x][i].first, x);
		}
	}
	return pod[x];
}

int centroid(int x, int prosl){
	for(int i=0; i<ms[x].size(); i++){
		if(ms[x][i].first!=prosl){
			if(pod[ms[x][i].first]>n/2){
				return centroid(ms[x][i].first, x);
			}
		}
	}
	return x;
}

ll izracunaj(int x, int prosl, ll put){
	ll sol=put*vrij[x];
	for(int i=0; i<ms[x].size(); i++){
		if(ms[x][i].first!=prosl){
			sol+=izracunaj(ms[x][i].first, x, put+ms[x][i].second);
		}
	}
	return sol;
}



int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> turist[i].first >> turist[i].second;
	}
	for(int i=0; i<n; i++){
		resi(i, turist[i].first, turist[i].second, 0, 0);
	}
	sort(put, put+n, cmp);
/*	for(int i=0; i<n; i++){
		for(int j=0; j<put[i].size(); j++){
			cout << put[i][j].first << " " << put[i][j].second << '\n';
		}
		cout << '\n';
	}*/
	int gran=n;
	for(int i=0; i<n; i++){
		if(!put[i].empty() && !put[i].back().second){
			gran=i;
			break;
		}
	}
	napravi(0, {0, 0}, 0, gran);
	napravi(0, {0, 0}, gran, n);
	br++;
/*	for(int i=0; i<br; i++){
		cout << "na " << i << " " << vrij[i] << '\n';
		for(int j=0; j<ms[i].size(); j++){
			cout << ms[i][j].first << " ";
		}
		cout << '\n';
	}*/
	dfs(0, 0);
	int c=centroid(0, 0);
	cout << izracunaj(c, c, 0) << '\n';
	return 0;
}

Compilation message

cvenk.cpp: In function 'int dfs(int, int)':
cvenk.cpp:104:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms[x].size(); i++){
               ~^~~~~~~~~~~~~
cvenk.cpp: In function 'int centroid(int, int)':
cvenk.cpp:113:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms[x].size(); i++){
               ~^~~~~~~~~~~~~
cvenk.cpp: In function 'll izracunaj(int, int, ll)':
cvenk.cpp:125:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms[x].size(); i++){
               ~^~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 49664 KB Output is correct
2 Correct 26 ms 49656 KB Output is correct
3 Correct 26 ms 49664 KB Output is correct
4 Correct 26 ms 49664 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 49664 KB Output is correct
2 Correct 28 ms 49664 KB Output is correct
3 Correct 27 ms 49656 KB Output is correct
4 Correct 28 ms 49664 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 55416 KB Output is correct
2 Correct 438 ms 56056 KB Output is correct
3 Correct 258 ms 54128 KB Output is correct
4 Correct 262 ms 54264 KB Output is correct
5 Correct 253 ms 54264 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 777 ms 92796 KB Output is correct
2 Correct 762 ms 93048 KB Output is correct
3 Correct 365 ms 62456 KB Output is correct
4 Correct 345 ms 60796 KB Output is correct
5 Correct 336 ms 60036 KB Output is correct