oj.uz

Submission #698535

# Submission time Handle Problem Language Result Execution time Memory
698535 2023-02-13T17:28:36 Z Half Ideal city (IOI12_city) C++17
100 / 100
 151 ms 22676 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3760 KB Output is correct
2 Correct 22 ms 3868 KB Output is correct
3 Correct 59 ms 9072 KB Output is correct
4 Correct 59 ms 9156 KB Output is correct
5 Correct 125 ms 17368 KB Output is correct
6 Correct 130 ms 17496 KB Output is correct
7 Correct 129 ms 17564 KB Output is correct
8 Correct 127 ms 17300 KB Output is correct
9 Correct 130 ms 17796 KB Output is correct
10 Correct 129 ms 22676 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4260 KB Output is correct
2 Correct 27 ms 4312 KB Output is correct
3 Correct 74 ms 10392 KB Output is correct
4 Correct 69 ms 10080 KB Output is correct
5 Correct 151 ms 20460 KB Output is correct
6 Correct 138 ms 18944 KB Output is correct
7 Correct 151 ms 20648 KB Output is correct
8 Correct 141 ms 18980 KB Output is correct
9 Correct 132 ms 18408 KB Output is correct
10 Correct 140 ms 18296 KB Output is correct