oj.uz

Submission #1016328

# Submission time Handle Problem Language Result Execution time Memory
1016328 2024-07-07T19:28:04 Z amirhoseinfar1385 Ideal city (IOI12_city) C++17
100 / 100
 204 ms 24392 KB 
#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10;
long long n,mod=1e9,vis[maxn];
vector<pair<long long,long long>>all;
vector<long long>adj[maxn],adja[maxn];
map<pair<long long,long long>,long long>mp;
long long mainres=0;

struct dsu{
  long long par[maxn],sz[maxn];
  dsu(){
    for(long long i=0;i<maxn;i++){
      par[i]=i;
      sz[i]=1;
    }
  }
  long long root(long long u){
    if(u==par[u]){
      return u;
    }
    return par[u]=root(par[u]);
  }
  long long con(long long u,long long v){
    long long rootu=root(u),rootv=root(v);
    if(rootu!=rootv){
      par[rootu]=rootv;
      sz[rootv]+=sz[rootu];
      sz[rootu]=0;
      return 1;
    }
    return 0;
  }
}ds1,ds2;

long long dfs(long long u,long long par=-1){
  vis[u]=ds1.sz[u];
  sort(adj[u].begin(),adj[u].end());
  adj[u].resize(unique(adj[u].begin(),adj[u].end())-adj[u].begin());
  long long ret=ds1.sz[u];
  for(auto x:adj[u]){
    if(x!=par){
      ret+=dfs(x,u);
    }
  }
//  cout<<u<<" "<<ret<<endl;
  mainres+=(n-ret)*ret;
  return ret;
}

long long solve2(){
  for(long long i=0;i<n;i++){
    mp[all[i]]=i;
  }
  for(long long i=0;i<n;i++){
    if(mp.count(make_pair(all[i].first,all[i].second+1))!=0){
      ds1.con(mp[make_pair(all[i].first,all[i].second+1)],i);
    }
    if(mp.count(make_pair(all[i].first+1,all[i].second))!=0){
      ds2.con(mp[make_pair(all[i].first+1,all[i].second)],i);
    }
  }
  for(long long i=0;i<n;i++){
    if(mp.count(make_pair(all[i].first,all[i].second+1))!=0){
      long long u=ds2.root(i);
      long long v=ds2.root(mp[make_pair(all[i].first,all[i].second+1)]);
      adja[u].push_back(v);
      adja[v].push_back(u);
    }
    if(mp.count(make_pair(all[i].first+1,all[i].second))!=0){
      long long u=ds1.root(i);
      long long v=ds1.root(mp[make_pair(all[i].first+1,all[i].second)]);
      adj[u].push_back(v);
      adj[v].push_back(u);
    }
  }
  dfs(ds1.root(0));
  for(long long i=0;i<n;i++){
    vis[i]=0;
    swap(ds1.sz[i],ds2.sz[i]);
    swap(adj[i],adja[i]);
  }
  dfs(ds2.root(0));
  mainres%=mod;
  return mainres;
}

int DistanceSum(int N,int *X,int *Y){
  n=N;
  for(long long i=0;i<n;i++){
    all.push_back(make_pair(X[i],Y[i]));
  }
  return solve2();
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 3 ms 8796 KB Output is correct
3 Correct 3 ms 8796 KB Output is correct
4 Correct 3 ms 8796 KB Output is correct
5 Correct 3 ms 9052 KB Output is correct
6 Correct 4 ms 9052 KB Output is correct
7 Correct 4 ms 9052 KB Output is correct
8 Correct 3 ms 9048 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 3 ms 9052 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 11476 KB Output is correct
2 Correct 31 ms 11796 KB Output is correct
3 Correct 81 ms 15820 KB Output is correct
4 Correct 85 ms 15564 KB Output is correct
5 Correct 173 ms 24008 KB Output is correct
6 Correct 190 ms 23316 KB Output is correct
7 Correct 181 ms 23240 KB Output is correct
8 Correct 204 ms 24008 KB Output is correct
9 Correct 189 ms 22308 KB Output is correct
10 Correct 157 ms 24392 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 11144 KB Output is correct
2 Correct 29 ms 11476 KB Output is correct
3 Correct 80 ms 15356 KB Output is correct
4 Correct 84 ms 15820 KB Output is correct
5 Correct 174 ms 22216 KB Output is correct
6 Correct 184 ms 23244 KB Output is correct
7 Correct 178 ms 22472 KB Output is correct
8 Correct 191 ms 23244 KB Output is correct
9 Correct 185 ms 23120 KB Output is correct
10 Correct 183 ms 23124 KB Output is correct