Submission #973143

#	Time	Username	Problem	Language	Result	Execution time	Memory
973143		12345678	Ideal city (IOI12_city)	C++17	100 / 100	129 ms	23788 KiB

city

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5, mod=1e9;

ll n, t, sz[nx], dp[nx], res;
set<ll> d[nx];
map<ll, vector<ll>> mpx, mpy;
map<pair<ll, ll>, ll> mp;

void dfs(int u, int p)
{
    dp[u]=sz[u];
    for (auto v:d[u]) if (v!=p) dfs(v, u), dp[u]+=dp[v];
    res+=(dp[u])*(n-dp[u]);
    //cout<<"debug "<<u<<' '<<dp[u]<<' '<<res<<'\n';
}

int DistanceSum(int N, int *X, int *Y) {
    n=N;
    for (int i=0; i<N; i++) mpx[X[i]].push_back(Y[i]), mpy[Y[i]].push_back(X[i]);
    for (auto [x, y]:mpx) 
    {
        sort(y.begin(), y.end());
        ++t;
        if (mp.find({x-1, y[0]})!=mp.end()) d[mp[{x-1, y[0]}]].insert(t), d[t].insert(mp[{x-1, y[0]}]);
        mp[{x, y[0]}]=t;
        sz[t]=1;
        for (int i=1; i<y.size(); i++)
        {
            if (y[i]-1!=y[i-1]) t++;
            sz[t]++;
            mp[{x, y[i]}]=t;
            if (mp.find({x-1, y[i]})!=mp.end()) d[mp[{x-1, y[i]}]].insert(t), d[t].insert(mp[{x-1, y[i]}]);
        }
    }
    dfs(1, 1);
    for (int i=1; i<=t; i++) d[i].clear(),sz[i]=0;
    t=0;
    mp.clear();
    for (auto [x, y]:mpy)
    {
        sort(y.begin(), y.end());
        ++t;
        if (mp.find({x-1, y[0]})!=mp.end()) d[mp[{x-1, y[0]}]].insert(t), d[t].insert(mp[{x-1, y[0]}]);
        mp[{x, y[0]}]=t;
        sz[t]=1;
        for (int i=1; i<y.size(); i++)
        {
            if (y[i]-1!=y[i-1]) t++;
            sz[t]++;
            mp[{x, y[i]}]=t;
            if (mp.find({x-1, y[i]})!=mp.end()) d[mp[{x-1, y[i]}]].insert(t), d[t].insert(mp[{x-1, y[i]}]);
        }
    }
    dfs(1, 1);
    /*
    for (int i=1; i<=t; i++)
    {
        cout<<"size "<<sz[i]<<':';
        for (auto x:d[i]) cout<<x<<' '; 
        cout<<'\n';
    }*/
    return res%mod;
}

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:32:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for (int i=1; i<y.size(); i++)
      |                       ~^~~~~~~~~
city.cpp:51:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for (int i=1; i<y.size(); i++)
      |                       ~^~~~~~~~~

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