Submission #846346

#	Time	Username	Problem	Language	Result	Execution time	Memory
846346		vjudge1	ČVENK (COI15_cvenk)	C++17	38 / 100	3019 ms	312984 KiB

cvenk

#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);
map<array<int, 2>, int> mp;
int sum = 0;


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]);
    }

    sum+=val[x]*z;
}

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;

    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);


    
    int ans = 1e18;

    for(int i=0; i<cnt; i++){
        sum=0;
    /*    for(auto l: a[i]){
            cout<<l[0]<<" "<<"\n";
        }
      */ dfs(i, i, 0);
      // cout<<i<<" "<<sum<<"\n";
        ans =min(ans, sum);
    }      

    cout<<ans<<"\n";
} 

Compilation message (stderr)

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:40: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]
   40 |         if(dep<adj[ve[0][1]].size())  aa.push_back({adj[ve[0][1]][dep][1] , ve[0][1]});
      |            ~~~^~~~~~~~~~~~~~~~~~~~~
cvenk.cpp:42: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]
   42 |         for(int i=1; i<ve.size(); i++){
      |                      ~^~~~~~~~~~
cvenk.cpp:55: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]
   55 |             if(dep<adj[ve[i][1]].size()){
      |                ~~~^~~~~~~~~~~~~~~~~~~~~
cvenk.cpp:74: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]
   74 |         if(dep<adj[ve[0][1]].size())  aa.push_back({adj[ve[0][1]][dep][0], ve[0][1]});
      |            ~~~^~~~~~~~~~~~~~~~~~~~~
cvenk.cpp:76: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]
   76 |         for(int i=1; i<ve.size(); i++){
      |                      ~^~~~~~~~~~
cvenk.cpp:89: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]
   89 |             if(dep<adj[ve[i][1]].size()){
      |                ~~~^~~~~~~~~~~~~~~~~~~~~
cvenk.cpp: In function 'int main()':
cvenk.cpp:132: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]
  132 |         for(int i=0; i<as.size(); i++){
      |                      ~^~~~~~~~~~
cvenk.cpp:136: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]
  136 |             if(i==as.size()-1||as[i][1]!=as[i+1][1]){
      |                ~^~~~~~~~~~~~~
cvenk.cpp:116:13: warning: unused variable 'cx' [-Wunused-variable]
  116 |         int cx=0, cy=0;
      |             ^~
cvenk.cpp:116:19: warning: unused variable 'cy' [-Wunused-variable]
  116 |         int cx=0, cy=0;
      |                   ^~

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40