Submission #225081

#TimeUsernameProblemLanguageResultExecution timeMemory
225081mehrdad_sohrabiČVENK (COI15_cvenk)C++14
60 / 100
668 ms184828 KiB
#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]; 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; // cout << b[i].F.F << " " << b[i].F.S << endl; // 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[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 (stderr)

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:101:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=1;i<a.size();i++){
                  ~^~~~~~~~~
cvenk.cpp:104: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);
         ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...