oj.uz

Submission #220371

# Submission time Handle Problem Language Result Execution time Memory
220371 2020-04-07T18:42:25 Z FieryPhoenix Ideal city (IOI12_city) C++11
23 / 100
 295 ms 15992 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<int>s;
    for (int j:row[i])
      s.insert(root(j));
    for (int x:s){
      ans+=(ll)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<int>s;
    for (int j:col[i])
      s.insert(root(j));
    for (int x:s){
      ans+=(ll)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 8 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 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 7040 KB Output is correct
2 Correct 48 ms 7152 KB Output is correct
3 Correct 114 ms 9984 KB Output is correct
4 Correct 123 ms 10104 KB Output is correct
5 Correct 267 ms 15096 KB Output is correct
6 Correct 295 ms 15736 KB Output is correct
7 Correct 256 ms 15992 KB Output is correct
8 Correct 281 ms 15736 KB Output is correct
9 Correct 289 ms 15696 KB Output is correct
10 Correct 252 ms 15864 KB Output is correct

Subtask #4
0 / 45.0

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