| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 846362 |
2023-09-07T14:02:15 Z |
vjudge1 |
ČVENK (COI15_cvenk) |
C++17 |
|
998 ms |
363888 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+37;
vector<array<int, 2>> adj[N];
vector<array<int, 2>> a[N*65];
vector<int> val(N*65), s(N*65);
map<array<int, 2>, int> mp;
int sum = 0, all, ans=1e18;;
void dfs(int x, int y, int z){
for(auto i: a[x]){
if(i[0]==y) continue;
dfs(i[0], x, z+i[1]);
s[x]+=s[i[0]];
}
s[x]+=val[x];
sum+=val[x]*z;
}
void dfs2(int x, int y, int val){
ans = min(ans, val);
for(auto i: a[x]){
if(i[0]==y) continue;
dfs2(i[0], x, val+i[1]*(all-2*s[i[0]]));
}
}
void op(int v, array<int, 2> pos, vector<array<int, 2>> ve, char type, int dep){
if(ve.size()==0) return;
if(type == 'x'){
sort(ve.begin(), ve.end());
int gh = mp[{ve[0][0], pos[1]}];
a[v].push_back({gh, ve[0][0]-pos[0]});
a[gh].push_back({v, ve[0][0]-pos[0]});
int tmp = gh;
vector<array<int, 2>> aa;
if(dep<adj[ve[0][1]].size()) aa.push_back({adj[ve[0][1]][dep][1] , ve[0][1]});
for(int i=1; i<ve.size(); i++){
if(ve[i][0]!=ve[i-1][0]){
op(tmp, {ve[i-1][0], pos[1]}, aa, 'y', dep+1);
aa.clear();
gh =mp[{ve[i][0], pos[1]}];
a[tmp].push_back({gh, ve[i][0]-ve[i-1][0]});
a[gh].push_back({tmp, ve[i][0]-ve[i-1][0]});
tmp = gh;
}
if(dep<adj[ve[i][1]].size()){
aa.push_back({adj[ve[i][1]][dep][1], ve[i][1]});
}
}
op(tmp, {ve[ve.size()-1][0], pos[1]}, aa, 'y', dep+1);
aa.clear();
}
else{
sort(ve.begin(), ve.end());
int gh = mp[{pos[0], ve[0][0]}];
a[v].push_back({gh, ve[0][0]-pos[1]});
a[gh].push_back({v, ve[0][0]-pos[1]});
int tmp = gh;
vector<array<int, 2>> aa;
if(dep<adj[ve[0][1]].size()) aa.push_back({adj[ve[0][1]][dep][0], ve[0][1]});
for(int i=1; i<ve.size(); i++){
if(ve[i][0]!=ve[i-1][0]){
op(tmp, {pos[0], ve[i-1][0]}, aa, 'x', dep+1);
aa.clear();
gh =mp[{pos[0], ve[i][0]}];
a[tmp].push_back({gh, ve[i][0]-ve[i-1][0]});
a[gh].push_back({tmp,ve[i][0]-ve[i-1][0] });
tmp = gh;
}
if(dep<adj[ve[i][1]].size()){
aa.push_back({adj[ve[i][1]][dep][0], ve[i][1]});
}
}
op(tmp, {pos[0], ve[ve.size()-1][0]}, aa, 'x', dep+1);
aa.clear();
}
}
signed main(){
ios_base::sync_with_stdio(false);
int n; cin >> n;
all=n;
int cnt = 1;
mp[{0, 0}]=0;
// cout<<0<<" "<<0 << " "<<0<<"\n";
vector<array<int, 2>> yy, xx;
for(int l=0; l<n; l++){
int x, y; cin >> x >> y;
adj[l].push_back({x, y});
int cx=0, cy=0;
vector<array<int, 2>> as;
int tmpx=x, tmpy=y;
for(int i=0; i<30&&x&&y; i++){
if(x&(1<<i)){
x-=(1<<i);
as.push_back({i, 0});
}else if(y&(1<<i)){
y-=(1<<i);
as.push_back({i, 1});
}
}
x=tmpx; y=tmpy;
for(int i=0; i<as.size(); i++){
if(as[i][1]==0) x-=(1<<as[i][0]);
else y-=(1<<as[i][0]);
if(i==as.size()-1||as[i][1]!=as[i+1][1]){
adj[l].push_back({x, y});
}
}
reverse(adj[l].begin(), adj[l].end());
for(auto i: adj[l]){
if(!mp.count(i)){
mp[i]=cnt, cnt++;
// cout<<cnt-1<<" "<<i[0]<<" "<<i[1]<<"\n";
}
}
val[mp[{tmpx, tmpy}]]++;
if(x==0){
yy.push_back({y, l});
}
else if(y==0){
xx.push_back({x, l});
}
}
op(0,{0, 0}, yy,'y', 1);
op(0, {0, 0}, xx, 'x', 1);
sum=0;
dfs(0, 0, 0);
dfs2(0, 0, sum);
cout<<ans<<"\n";
}
Compilation message
cvenk.cpp: In function 'void op(long long int, std::array<long long int, 2>, std::vector<std::array<long long int, 2> >, char, long long int)':
cvenk.cpp:50:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | if(dep<adj[ve[0][1]].size()) aa.push_back({adj[ve[0][1]][dep][1] , ve[0][1]});
| ~~~^~~~~~~~~~~~~~~~~~~~~
cvenk.cpp:52:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int i=1; i<ve.size(); i++){
| ~^~~~~~~~~~
cvenk.cpp:65:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | if(dep<adj[ve[i][1]].size()){
| ~~~^~~~~~~~~~~~~~~~~~~~~
cvenk.cpp:84:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | if(dep<adj[ve[0][1]].size()) aa.push_back({adj[ve[0][1]][dep][0], ve[0][1]});
| ~~~^~~~~~~~~~~~~~~~~~~~~
cvenk.cpp:86:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int i=1; i<ve.size(); i++){
| ~^~~~~~~~~~
cvenk.cpp:99:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | if(dep<adj[ve[i][1]].size()){
| ~~~^~~~~~~~~~~~~~~~~~~~~
cvenk.cpp: In function 'int main()':
cvenk.cpp:142:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for(int i=0; i<as.size(); i++){
| ~^~~~~~~~~~
cvenk.cpp:146:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | if(i==as.size()-1||as[i][1]!=as[i+1][1]){
| ~^~~~~~~~~~~~~
cvenk.cpp:126:13: warning: unused variable 'cx' [-Wunused-variable]
126 | int cx=0, cy=0;
| ^~
cvenk.cpp:126:19: warning: unused variable 'cy' [-Wunused-variable]
126 | int cx=0, cy=0;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
257136 KB |
Output is correct |
| 2 |
Correct |
46 ms |
257104 KB |
Output is correct |
| 3 |
Correct |
47 ms |
257080 KB |
Output is correct |
| 4 |
Correct |
47 ms |
257192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
257236 KB |
Output is correct |
| 2 |
Correct |
46 ms |
257104 KB |
Output is correct |
| 3 |
Correct |
49 ms |
257360 KB |
Output is correct |
| 4 |
Correct |
47 ms |
257272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
155 ms |
268904 KB |
Output is correct |
| 2 |
Correct |
155 ms |
268976 KB |
Output is correct |
| 3 |
Correct |
80 ms |
263452 KB |
Output is correct |
| 4 |
Correct |
79 ms |
263620 KB |
Output is correct |
| 5 |
Correct |
93 ms |
263932 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
998 ms |
363824 KB |
Output is correct |
| 2 |
Correct |
966 ms |
363888 KB |
Output is correct |
| 3 |
Correct |
199 ms |
283436 KB |
Output is correct |
| 4 |
Correct |
211 ms |
278600 KB |
Output is correct |
| 5 |
Correct |
178 ms |
277528 KB |
Output is correct |
