Submission #1238745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238745		caacrugon	Ideal city (IOI12_city)	C++20	55 / 100	62 ms	1864 KiB

city

#include <bits/stdc++.h>
using namespace std;
#define mkp make_pair
 
#define ll long long
 
ll sumM(vector<int>&A){
  sort(A.begin(),A.end());
  ll ans=0,sum=0;
  for(int i=0;i<A.size();i++){
    ans+=1LL*A[i]*i-sum;
    sum+=A[i];
  }
  return ans%1000000000;
}
 
int DistanceSum(int N,int*X,int*Y){
  if(N>2000){
    vector<int> lnx(X,X+N),lny(Y,Y+N);
    return (sumM(lnx)+sumM(lny))%1000000000;
  }else{
    map<pair<int,int>,int> nodes;
    for(int i=0;i<N;i++){
      nodes[mkp(X[i],Y[i])]=i;
    }
    vector<vector<int>> ln(N);
    for(auto&e:nodes){
        int x=e.first.first,y=e.first.second,i=e.second;
        if(nodes.count(mkp(x+1,y)))ln[i].push_back(nodes[mkp(x+1,y)]);
        if(nodes.count(mkp(x-1,y)))ln[i].push_back(nodes[mkp(x-1,y)]);
        if(nodes.count(mkp(x,y+1)))ln[i].push_back(nodes[mkp(x,y+1)]);
        if(nodes.count(mkp(x,y-1)))ln[i].push_back(nodes[mkp(x,y-1)]);
    }
    int ans=0;
    for(int i=0;i<N;i++){
        queue<int> q;
        q.push(i);
        vector<int> dist(N,-1);
        dist[i]=0;
        while(q.size()){
            int nodo=q.front();q.pop();
            for(int v:ln[nodo]){
              if(dist[v]<0){
                  dist[v]=dist[nodo]+1;
                  q.push(v);
              }
            }
        }
        for(int j=i+1;j<N;j++){
          if(dist[j]>=0){
            ans=(ans+dist[j])%1000000000;
          }
        }
    }
    return ans;
  }
}

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 0 / 45