제출 #249319

#제출 시각아이디문제언어결과실행 시간메모리
249319vanicČVENK (COI15_cvenk)C++14
78 / 100
3081 ms92792 KiB
#include <iostream> #include <cstdio> #include <math.h> #include <algorithm> #include <vector> #include <bitset> 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); /* 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...