| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 249326 |
2020-07-14T16:11:04 Z |
vanic |
ČVENK (COI15_cvenk) |
C++14 |
|
345 ms |
127552 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);
}
}
int br;
bool cmp(vector < pair < int, int > > a, vector < pair < int, int > > b){
if(a.empty()){
return 1;
}
if(b.empty()){
return 0;
}
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);
assert(0);
/* 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:101: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:110: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:122:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<ms[x].size(); i++){
~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
77 ms |
100472 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
83 ms |
100472 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
278 ms |
111464 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
345 ms |
127552 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
