Submission #698535

#	Time	Username	Problem	Language	Result	Execution time	Memory
698535		Half	Ideal city (IOI12_city)	C++17	100 / 100	151 ms	22676 KiB

city

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"WAFFLES "<<i<<"<\n"
#define INF 1000000000000000000LL
#define EPS (0.00000000001L)
#define pi (3.141592653589793L)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000000LL;

template<class A=ll>
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

class DSU
{
    public:
    ll N;
    vector<ll> p,siz;

    DSU(ll n)
    {
        N=n; REP(i,0,N) {p.pb(i); siz.pb(1);}
    }

    ll find(ll x)
    {
        if(p[x]==x) {return x;}
        return p[x] = find(p[x]);
    }

    ll sizee(ll x){
        return siz[find(x)];
    }

    void unionn(ll a, ll b)
    {
        a=find(a); b=find(b);
    if(a==b) {return;}
        if(siz[a]>siz[b]) {swap(a,b);}
        p[a]=b; siz[b]+=siz[a];
    }
};

ll dfs(ll n, vector<vector<ll>>& adj, vector<ll>& wgt, vector<vector<ll>>& dir_wgt, ll nd, ll pr){

  dir_wgt[nd].assign(adj[nd].size(), 0);
  ll sm = 0;
  ll pr_i = -1;
  for(ll i = 0; i < (ll)adj[nd].size(); ++i){
    ll nb = adj[nd][i];
    if(nb == pr){
      pr_i = i;
      continue;
    }
    sm += (dir_wgt[nd][i] = dfs(n, adj, wgt, dir_wgt, nb, nd));
  }
  if(pr_i != -1)
    dir_wgt[nd][pr_i] = n - sm - wgt[nd];
  return sm + wgt[nd];
}

ll DistSumX(int n, const vector<int>& x, const vector<int>& y){

  vector<pair<ll, ll>> crd(n);
  map<pair<ll, ll>, ll> crd_map;
  for(ll i = 0; i < n; ++i){
    crd[i] = {x[i], y[i]};
  }
  sort(crd.begin(), crd.end());
  for(ll i = 0; i < n; ++i){
    crd_map[crd[i]] = i;
  }
  DSU dsu(n);
  for(ll i = 1; i < n; ++i){
    if(crd[i].ff == crd[i-1].ff && crd[i].ss-1 == crd[i-1].ss)
      dsu.unionn(i, i-1);
  }
  vector<vector<ll>> adj(n);
  vector<ll> wgt(n, -1);
  for(ll i = 1; i < n; ++i){
    ll xi = crd[i].ff, yi = crd[i].ss;
    if(crd_map.find({xi-1, yi}) != crd_map.end()){
      if(adj[dsu.find(i)].size() == 0 || adj[dsu.find(i)].back() != dsu.find(crd_map[{xi-1, yi}])){
        adj[dsu.find(i)].pb(dsu.find(crd_map[{xi-1, yi}]));
        adj[dsu.find(crd_map[{xi-1, yi}])].pb(dsu.find(i));
      }
    }
    wgt[dsu.find(i)] = dsu.sizee(i);
  }
  vector<vector<ll>> dir_wgt(n);
  dfs(n, adj, wgt, dir_wgt, dsu.find(0), -1);
  ll ans = 0;
  for(ll i = 0; i < n; ++i){
    for(ll j = 0; j < (ll)dir_wgt[i].size(); ++j){
      if(i < adj[i][j]){
        ans += dir_wgt[i][j] * (n - dir_wgt[i][j]);
        ans = ans % mod;
      }
    }
  }
  return ans % mod;
}

int DistanceSum(int N, int *X, int *Y) {
  vector<int> x(N), y(N);
  for(ll i = 0; i < N; ++i){
    x[i] = X[i];
    y[i] = Y[i];
  }
  ll sol = 0;
  sol += DistSumX(N, x, y);
  sol += DistSumX(N, y, x);
  return sol % mod;

}

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