이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <bitset>
using namespace std;
const int maxn=1e5+5, maxm=3e6;
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);
/* 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].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;
}
컴파일 시 표준 에러 (stderr) 메시지
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |