oj.uz

Submission #220370

# Submission time Handle Problem Language Result Execution time Memory
220370 2020-04-07T18:41:26 Z FieryPhoenix Ideal city (IOI12_city) C++11
0 / 100
 270 ms 15736 KB 
#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000000

int N,X[100001],Y[100001];
int minX=INF,minY=INF;
map<pair<int,int>,int>mp; 
vector<int>row[100005],col[100005];
ll ans;
int rt[100005],siz[100005];

void reset(){
  for (int i=0;i<N;i++){
    rt[i]=i;
    siz[i]=1;
  }
}

int root(int x){
  while (x!=rt[x]){
    rt[x]=rt[rt[x]];
    x=rt[x];
  }
  return x;
}

void merge(int a, int b){
  a=root(a);
  b=root(b);
  if (a==b) return;
  if (siz[a]<siz[b]) swap(a,b);
  rt[b]=a;
  siz[a]+=siz[b];
}

void sweepRow(){
  reset();
  for (int i=1;i<=N;i++){
    for (int j:row[i]){
      if (X[j]>1 && mp.count({X[j]-1,Y[j]}))
	merge(j,mp[{X[j]-1,Y[j]}]);
      if (Y[j]>1 && mp.count({X[j],Y[j]-1}))
	merge(j,mp[{X[j],Y[j]-1}]);
      if (Y[j]<N && mp.count({X[j],Y[j]+1}))
	merge(j,mp[{X[j],Y[j]+1}]);
    }
    set<ll>s;
    for (int j:row[i])
      s.insert(root(j));
    for (ll x:s){
      ans+=siz[x]*(N-siz[x]);
    }
    ans%=MOD;
  }
}

void sweepCol(){
  reset();
  for (int i=1;i<=N;i++){
    for (int j:col[i]){
      if (X[j]>1 && mp.count({X[j]-1,Y[j]}))
	merge(j,mp[{X[j]-1,Y[j]}]);
      if (X[j]<N && mp.count({X[j]+1,Y[j]}))
	merge(j,mp[{X[j]+1,Y[j]}]);
      if (Y[j]>1 && mp.count({X[j],Y[j]-1}))
	merge(j,mp[{X[j],Y[j]-1}]);
    }
    set<ll>s;
    for (int j:col[i])
      s.insert(root(j));
    for (ll x:s){
      ans+=siz[x]*(N-siz[x]);
    }
    ans%=MOD;
  }
}

int DistanceSum(int n, int x[], int y[]){
  N=n;
  for (int i=0;i<N;i++){
    X[i]=x[i];
    Y[i]=y[i];
    minX=min(minX,X[i]);
    minY=min(minY,Y[i]);
  }
  for (int i=0;i<N;i++){
    X[i]-=(minX-1);
    Y[i]-=(minY-1);
    mp[{X[i],Y[i]}]=i;
    row[X[i]].push_back(i);
    col[Y[i]].push_back(i);
  }
  sweepRow();
  sweepCol();
  return ans;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 5300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 7296 KB Output is correct
2 Correct 47 ms 7296 KB Output is correct
3 Correct 119 ms 10360 KB Output is correct
4 Correct 121 ms 10360 KB Output is correct
5 Incorrect 270 ms 15736 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -