Submission #224958

#	Time	Username	Problem	Language	Result	Execution time	Memory
224958		mehrdad_sohrabi	ČVENK (COI15_cvenk)	C++14	0 / 100	3084 ms	277500 KiB

cvenk

#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=3e5+100,M=60;
vector <int> g[N];
map <pii,int> mp;
ll w[N*M];
pii nod[N*M];
ll par[N*M];
ll sz[N];
ll dp[N];
ll dis[N];
ll n;
ll ma=(ll)1e15;
ll dfssz(ll v){
    sz[v]=w[v];
    for (auto u : g[v]){
        dfssz(u);
        sz[v]+=sz[u];
    }
}
ll dfsdp(ll v){
    for (auto u : g[v]){
        dfsdp(u);
        dp[v]+=dp[u];
        ll e=nod[u].F-nod[v].F+nod[u].S-nod[v].S;
        dp[v]+=sz[u]*e;
    }
}
ll dfs(ll v){
    ma=min(ma,dp[v]);
    for (auto u : g[v]){
        ll e=nod[u].F-nod[v].F+nod[u].S-nod[v].S;
        dp[u]=dp[v]+e*n-2*e*sz[u];
        dfs(u);
    }
}
int32_t main(){
    cin >> n;
    vector <pii> a;
    ll cnt=2;
    mp[{0,0}]=1;
    nod[1]={0,0};
    for (int i=0;i<n;i++){
        ll r,s;
        cin >> r >> s;

            ll x=0,y=0,f=0;
            for (int j=M/2;j>-1;j--){
                if (r-x>=s-y){
                    ll z=x,t=y;
                    if ((r-x)>=(1<<j)){
                        x+=(1<<j);
                    }
                    if (mp[{x,y}]==0){
                        nod[cnt]={x,y};
                        par[cnt]=mp[{z,t}];
                        mp[{x,y}]=cnt++;
                    }
                    a.pb({x,y});
                    if ((s-y)>=(1<<j)){
                        y+=(1<<j);
                    }
                    a.pb({x,y});
                    if (mp[{x,y}]==0){
                        nod[cnt]={x,y};
                      //  cout << x << " " << y << endl;
                        par[cnt]=mp[{z,t}];
                        mp[{x,y}]=cnt++;
                    }
                }
                else{
                    ll z=x,t=y;
                    if ((s-y)>=(1<<j)){
                        y+=(1<<j);
                    }
                    a.pb({x,y});
                    if (mp[{x,y}]==0){
                        nod[cnt]={x,y};
                        par[cnt]=mp[{z,t}];
                      //  cout << x << " " << y << endl;
                        mp[{x,y}]=cnt++;
                    }
                    if ((r-x)>=(1<<j)){
                        x+=(1<<j);
                    }
                    if (mp[{x,y}]==0){
                        nod[cnt]={x,y};
                        par[cnt]=mp[{z,t}];
                       // cout << x << " " << y << endl;
                        mp[{x,y}]=cnt++;
                    }
                    a.pb({x,y});
                }
            }
        w[mp[{r,s}]]++;
    }
    a.pb({0,0});
    sort(a.begin(),a.end());
    a.resize(unique(a.begin(), a.end()) - a.begin());
    for (int i=1;i<a.size();i++){
        if (a[i].F==a[i-1].F && par[mp[a[i-1]]]==par[mp[a[i]]]){
            par[mp[a[i]]]=mp[a[i-1]];
        }
    }
   // cout << nod[par[mp[{2,1}]]].F << " argers " << nod[par[mp[{2,1}]]].S << endl;
    vector <pii> b;
    for (int i=0;i<a.size();i++){
        swap(a[i].F,a[i].S);
        b.pb(a[i]);
        swap(a[i].F,a[i].S);
    }
    sort(b.begin(),b.end());
    for (int i=1;i<b.size();i++){
        pii d=b[i],e=b[i-1];
        swap(d.F,d.S);
        swap(e.F,e.S);
        if (b[i].F==b[i-1].F && par[mp[e]]==par[mp[d]]){
            par[mp[d]]=mp[e];
           // cout << nod[par[mp[{2,1}]]].F << " argers " << nod[par[mp[{2,1}]]].S << endl;
        }
    }
    for (int i=1;i<a.size();i++){
        g[par[mp[a[i]]]].pb(mp[a[i]]);
      //  cout << par[mp[a[i]]] << " " << mp[a[i]] << " " << nod[mp[a[i]]].F << " " << nod[mp[a[i]]].S << " " <<  nod[par[mp[a[i]]]].F << " " << nod[par[mp[a[i]]]].S << endl;
    }
    dfssz(mp[{0,0}]);
    dfsdp(mp[{0,0}]);
//cout << dp[mp[{2,0}]] << endl;
    dfs(mp[{0,0}]);
    cout << ma << endl;


}
/*
9
28 0
25 4
20 9
20 0
18 13
16 12
16 5
4 9
10 16
*/

Compilation message (stderr)

cvenk.cpp: In function 'll dfssz(ll)':
cvenk.cpp:31:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
cvenk.cpp: In function 'll dfsdp(ll)':
cvenk.cpp:39:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
cvenk.cpp: In function 'll dfs(ll)':
cvenk.cpp:47:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
cvenk.cpp: In function 'int32_t main()':
cvenk.cpp:58:24: warning: unused variable 'f' [-Wunused-variable]
             ll x=0,y=0,f=0;
                        ^
cvenk.cpp:111:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=1;i<a.size();i++){
                  ~^~~~~~~~~
cvenk.cpp:118:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<a.size();i++){
                  ~^~~~~~~~~
cvenk.cpp:124:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=1;i<b.size();i++){
                  ~^~~~~~~~~
cvenk.cpp:133:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=1;i<a.size();i++){
                  ~^~~~~~~~~

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