oj.uz

Submission #225083

# Submission time Handle Problem Language Result Execution time Memory
225083 2020-04-19T09:19:29 Z mehrdad_sohrabi ČVENK (COI15_cvenk) C++14
100 / 100
 1249 ms 375664 KB 
#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=2e5+100,M=60;
vector <int> g[N*32];
map <pii,int> val;
int w[N*32];
pii nod[N*32];
int par[N*32];
int sz[N*32];
ll dp[N*32];
int n;
ll ma=(ll)1e15;
void dfssz(ll v){
    sz[v]=w[v];
    for (auto u : g[v]){
        dfssz(u);
        sz[v]+=sz[u];
    }
}
void 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]+=(ll)sz[u]*e;
    }
  //  cout << v << " " << sz[v] << endl;
}
void 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]=(ll)dp[v]+(ll)e*(ll)n-(ll)2*(ll)e*(ll)sz[u];
        dfs(u);
    }
}
int32_t main(){
    sync;
    scanf("%d",&n);
   // cin >> n;
    vector <pii> a;
    for (int i=0;i<n;i++){
        int r,s;
        scanf("%d %d",&r,&s);
        //cin >> r >> s;
        int f=r,h=s;
        int x=0,y=0;
        for (int j=M/2;j>-1;j--){
            int z=x,t=y;
            if ((r-x)>=(1<<j)){
                x+=(1<<j);
                a.pb({x,y});
            }
            if ((s-y)>=(1<<j)){
                y+=(1<<j);
                a.pb({x,y});
            }
        }
        //cout << 1 << endl;
        val[{r,s}]++;
    }
    a.pb({0,0});
    sort(a.begin(),a.end());
    a.resize(unique(a.begin(), a.end()) - a.begin());
    for (int i=0;i<a.size();i++){
        nod[i]=a[i];
    }
    for (int i=1;i<a.size();i++){
        if (a[i].F==a[i-1].F && ((a[i].F)&(a[i].S-1))==0 && a[i].S!=0){
            par[i]=i-1;
        }
    }
    vector <pair <pii,int> > b;
    for (int i=0;i<a.size();i++){
        swap(a[i].F,a[i].S);
        b.pb({a[i],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].F,e=b[i-1].F;
        swap(d.F,d.S);
        swap(e.F,e.S);
        if (b[i].F.F==b[i-1].F.F && ((d.F-1)&(d.S))==0 && d.F!=0){
            par[b[i].S]=b[i-1].S;
        }
    }
    for (int i=1;i<a.size();i++){
        g[par[i]].pb(i);
    }
    for (int i=0;i<a.size();i++){
        w[i]=val[a[i]];
    }
    dfssz(0);
    dfsdp(0);
    dfs(0);
   // cout << dp[1] << endl;
    printf("%lld",ma);
   // cout << ans-(1<<28);


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

Compilation message

cvenk.cpp: In function 'int32_t main()':
cvenk.cpp:60:17: warning: unused variable 'z' [-Wunused-variable]
             int z=x,t=y;
                 ^
cvenk.cpp:60:21: warning: unused variable 't' [-Wunused-variable]
             int z=x,t=y;
                     ^
cvenk.cpp:57:13: warning: unused variable 'f' [-Wunused-variable]
         int f=r,h=s;
             ^
cvenk.cpp:57:17: warning: unused variable 'h' [-Wunused-variable]
         int f=r,h=s;
                 ^
cvenk.cpp:76:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<a.size();i++){
                  ~^~~~~~~~~
cvenk.cpp:79:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=1;i<a.size();i++){
                  ~^~~~~~~~~
cvenk.cpp:85:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<a.size();i++){
                  ~^~~~~~~~~
cvenk.cpp:91:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=1;i<b.size();i++){
                  ~^~~~~~~~~
cvenk.cpp:99:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=1;i<a.size();i++){
                  ~^~~~~~~~~
cvenk.cpp:102:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<a.size();i++){
                  ~^~~~~~~~~
cvenk.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
cvenk.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&r,&s);
         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 150792 KB Output is correct
2 Correct 90 ms 150776 KB Output is correct
3 Correct 96 ms 150928 KB Output is correct
4 Correct 84 ms 150752 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 151164 KB Output is correct
2 Correct 89 ms 151032 KB Output is correct
3 Correct 86 ms 150936 KB Output is correct
4 Correct 87 ms 150976 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 167628 KB Output is correct
2 Correct 203 ms 167568 KB Output is correct
3 Correct 137 ms 159080 KB Output is correct
4 Correct 157 ms 159100 KB Output is correct
5 Correct 154 ms 159112 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1235 ms 375664 KB Output is correct
2 Correct 1249 ms 375532 KB Output is correct
3 Correct 594 ms 296732 KB Output is correct
4 Correct 678 ms 291184 KB Output is correct
5 Correct 730 ms 298028 KB Output is correct