Submission #382850

#	Time	Username	Problem	Language	Result	Execution time	Memory
382850		mehrdad_sohrabi	Ideal city (IOI12_city)	C++14	100 / 100	865 ms	26004 KiB

city

#include <bits/stdc++.h>
/// 500 485 462 A4
using namespace std;
typedef long long int ll;
typedef complex<double> point;
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;

#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
const int MAXN=2e5+100;
map <pii,int> mp;
map <pii,int> vis;
vector <int> g[MAXN];
ll sz[MAXN];
ll dis[MAXN];
void dfs(ll v){
    sz[v]=1;
    for (auto u : g[v]){
        dfs(u);
        sz[v]+=sz[u];
    }
}
void bfs(ll X,ll Y){
    memset(dis,63,sizeof dis);
    dis[mp[{X,Y}]]=0;
    queue <pii> q;
    q.push({X,Y});
    dis[0]=0;
    while(q.size()){
        ll x=q.front().F,y=q.front().S;
        q.pop();
        if (dis[mp[{x-1,y}]]>dis[mp[{x,y}]]+1){
            g[mp[{x,y}]].pb(mp[{x-1,y}]);
            dis[mp[{x-1,y}]]=dis[mp[{x,y}]]+1;
            q.push({x-1,y});
        }
        if (dis[mp[{x+1,y}]]>dis[mp[{x,y}]]+1){
            g[mp[{x,y}]].pb(mp[{x+1,y}]);
            dis[mp[{x+1,y}]]=dis[mp[{x,y}]]+1;
            q.push({x+1,y});
        }
        if (dis[mp[{x,y-1}]]>dis[mp[{x,y}]]+1){
            g[mp[{x,y}]].pb(mp[{x,y-1}]);
            dis[mp[{x,y-1}]]=dis[mp[{x,y}]]+1;
            q.push({x,y-1});
        }
        if (dis[mp[{x,y+1}]]>dis[mp[{x,y}]]+1){
            g[mp[{x,y}]].pb(mp[{x,y+1}]);
            dis[mp[{x,y+1}]]=dis[mp[{x,y}]]+1;
            q.push({x,y+1});
        }
    }
    dfs(mp[{X,Y}]);
}
ll hal(int N,int *X,int *Y){
    ll ans=0;
    for (int i=0;i<MAXN;i++) g[i].clear();
    mp.clear();
    vector <pii> a;
    for (int i=0;i<N;i++){
        a.pb({X[i],Y[i]});
    }
    sort(a.begin(),a.end());
    for (int i=0;i<a.size();i++){
        mp[a[i]]=i+1;
    }
    bfs(a.back().F,a.back().S);
    dis[0]=1e9;
    for (int i=0;i<a.size();i++){
        ll j=i;
        while(j<a.size() && a[j].F==a[i].F && a[j].S-a[i].S==j-i) j++;
     //   for (int k=i;k<j;k++){
     //       cout << a[k].F << " " << a[k].S << "   " ;
     //   }
   //     cout << endl;
        vector <ll> b;
        vector <ll> w;
        ll last=-1;
        ll p1=0;
        ll ss=0,zz=0;
        for (int k=i;k<j;k++){
            ll z=k;
            if (dis[mp[{a[k].F-1,a[k].S}]]<dis[mp[a[k]]]) p1=1;
            if (mp[{a[k].F-1,a[k].S}]==0 || dis[mp[{a[k].F-1,a[k].S}]]<dis[mp[a[k]]]) continue;
            ll mx=0;
            while(z<j && !(mp[{a[z].F-1,a[z].S}]==0 || dis[mp[{a[z].F-1,a[z].S}]]<dis[mp[a[z]]])){
                mx=max(mx,sz[mp[{a[z].F-1,a[z].S}]]);
                z++;
            }
            b.pb(mx);
            ss+=mx;
            k=z-1;
        }
        for (int k=i;k<j;k++){
            ll z=k;
            if (dis[mp[{a[k].F+1,a[k].S}]]<dis[mp[a[k]]]) p1=2;
            if (mp[{a[k].F+1,a[k].S}]==0 || dis[mp[{a[k].F+1,a[k].S}]]<dis[mp[a[k]]]) continue;
            ll mx=0;
            while(z<j && !(mp[{a[z].F+1,a[z].S}]==0 || dis[mp[{a[z].F+1,a[z].S}]]<dis[mp[a[z]]])){
                mx=max(mx,sz[mp[{a[z].F+1,a[z].S}]]);
                z++;
            }
            w.pb(mx);
            zz+=mx;
            k=z-1;

        }
     //   cout << p1 << " p1" << endl;
        ll h=N-ss-zz;
        if (p1==1){
            b.pb(h-(j-i));
            ss+=h-(j-i);
            w.clear();
            zz+=j-i;
            w.pb(zz);
        }
        else{
            w.clear();
            zz+=h;
            w.pb(zz);
        }
        ans+=ss*zz+ss*ss+zz*zz;
        for (auto u : b) ans-=u*u;

        for (auto u : w) ans-=u*u;
        i=j-1;
    }
    return ans;

}
int DistanceSum(int N, int *X, int *Y) {
    ll ans=hal(N,X,Y);
    ans+=hal(N,Y,X);
    return ans%(ll)(1e9);
}
/*
int main() {
  int tmp;

  char *inbuf, *outbuf;
  inbuf = (char*) malloc(inbuf_len * sizeof(char));
  outbuf = (char*) malloc(outbuf_len * sizeof(char));
  tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
  assert(tmp == 0);
  tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
  assert(tmp == 0);

  int N, i;
  tmp = scanf("%d", &N);
  assert(tmp == 1);
  int *sq_x, *sq_y;
  sq_x = (int*) malloc(N * sizeof(int));
  sq_y = (int*) malloc(N * sizeof(int));
  for (i = 0; i < N; i++) {
    tmp = scanf("%d %d", &sq_x[i], &sq_y[i]);
    assert(tmp == 2);
  }
  int ds = DistanceSum(N, sq_x, sq_y);
  printf("%d\n", ds);

  return 0;

}
20
3 5
4 6
2 5
3 4
6 5
1 6
2 7
3 1
2 6
1 5
5 5
5 4
4 7
4 2
3 2
3 3
4 4
4 3
4 5
5 2

*/

Compilation message (stderr)

city.cpp: In function 'll hal(int, int*, int*)':
city.cpp:73:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int i=0;i<a.size();i++){
      |                  ~^~~~~~~~~
city.cpp:78:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (int i=0;i<a.size();i++){
      |                  ~^~~~~~~~~
city.cpp:80:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         while(j<a.size() && a[j].F==a[i].F && a[j].S-a[i].S==j-i) j++;
      |               ~^~~~~~~~~
city.cpp:87:12: warning: unused variable 'last' [-Wunused-variable]
   87 |         ll last=-1;
      |            ^~~~

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45