oj.uz

Submission #973143

# Submission time Handle Problem Language Result Execution time Memory
973143 2024-05-01T14:28:00 Z 12345678 Ideal city (IOI12_city) C++17
100 / 100
 129 ms 23788 KB 
#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

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.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 4 ms 5468 KB Output is correct
6 Correct 3 ms 5436 KB Output is correct
7 Correct 3 ms 5468 KB Output is correct
8 Correct 4 ms 5212 KB Output is correct
9 Correct 3 ms 5412 KB Output is correct
10 Correct 3 ms 5212 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 7256 KB Output is correct
2 Correct 17 ms 7260 KB Output is correct
3 Correct 44 ms 10324 KB Output is correct
4 Correct 44 ms 10324 KB Output is correct
5 Correct 91 ms 15608 KB Output is correct
6 Correct 107 ms 15696 KB Output is correct
7 Correct 107 ms 16108 KB Output is correct
8 Correct 94 ms 15592 KB Output is correct
9 Correct 100 ms 15700 KB Output is correct
10 Correct 129 ms 23788 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8092 KB Output is correct
2 Correct 20 ms 7952 KB Output is correct
3 Correct 50 ms 12664 KB Output is correct
4 Correct 51 ms 11832 KB Output is correct
5 Correct 118 ms 20128 KB Output is correct
6 Correct 102 ms 17312 KB Output is correct
7 Correct 111 ms 20048 KB Output is correct
8 Correct 106 ms 17488 KB Output is correct
9 Correct 97 ms 16724 KB Output is correct
10 Correct 98 ms 16680 KB Output is correct