oj.uz

Submission #1016327

# Submission time Handle Problem Language Result Execution time Memory
1016327 2024-07-07T19:27:25 Z amirhoseinfar1385 Ideal city (IOI12_city) C++17
32 / 100
 8 ms 4308 KB 
#include<bits/stdc++.h>
using namespace std;
const long long maxn=2000+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 0 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct

Subtask #2
21.0 / 21.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 4308 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 4304 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -