oj.uz

Submission #220519

# Submission time Handle Problem Language Result Execution time Memory
220519 2020-04-08T03:25:40 Z FieryPhoenix Ideal city (IOI12_city) C++11
100 / 100
 324 ms 22772 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];
vector<int>adj[100005];
ll subsize[100005];
bool vis[100005];

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

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 dfs(int node, int par){
  vis[node]=true;
  subsize[node]=siz[node];
  for (int x:adj[node])
    if (x!=par && !vis[x]){
      dfs(x,node);
      subsize[node]+=subsize[x];
    }
  if (node!=par){
    ans+=subsize[node]*(N-subsize[node]);
    ans%=MOD;
  }
}
      
void solveRow(){
  reset();
  for (int i=1;i<=N;i++)
    for (int j:row[i]){
      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}]);
    }
  for (int i=1;i<=N;i++)
    for (int j:row[i]){
      if (X[j]>1 && mp.count({X[j]-1,Y[j]})){
	int a=root(j);
	int b=root(mp[{X[j]-1,Y[j]}]);
	adj[a].push_back(b);
	adj[b].push_back(a);
      }
    }
  dfs(root(0),root(0));
}

void solveCol(){
  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]}]);
    }
  for (int i=1;i<=N;i++)
    for (int j:col[i]){
      if (Y[j]>1 && mp.count({X[j],Y[j]-1})){
	int a=root(j);
	int b=root(mp[{X[j],Y[j]-1}]);
	adj[a].push_back(b);
	adj[b].push_back(a);
      }
    }
  dfs(root(0),root(0));
}

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);
  }
  solveRow();
  solveCol();
  return ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 9976 KB Output is correct
2 Correct 53 ms 10220 KB Output is correct
3 Correct 123 ms 14072 KB Output is correct
4 Correct 129 ms 13920 KB Output is correct
5 Correct 310 ms 20984 KB Output is correct
6 Correct 300 ms 20728 KB Output is correct
7 Correct 274 ms 21240 KB Output is correct
8 Correct 317 ms 21240 KB Output is correct
9 Correct 305 ms 20344 KB Output is correct
10 Correct 299 ms 22772 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 10104 KB Output is correct
2 Correct 51 ms 10360 KB Output is correct
3 Correct 127 ms 14328 KB Output is correct
4 Correct 128 ms 14324 KB Output is correct
5 Correct 300 ms 21368 KB Output is correct
6 Correct 297 ms 21240 KB Output is correct
7 Correct 314 ms 21496 KB Output is correct
8 Correct 297 ms 21112 KB Output is correct
9 Correct 324 ms 20984 KB Output is correct
10 Correct 300 ms 21112 KB Output is correct