oj.uz

Submission #696905

# Submission time Handle Problem Language Result Execution time Memory
696905 2023-02-07T15:07:57 Z whqkrtk04 Ideal city (IOI12_city) C++17
100 / 100
 53 ms 14212 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000000;
const ll LLINF = (ll)1e18+1;
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
ll mod(ll a, ll b) { return ((a%b) + b) % b; }

vector<int> compact(int N, int *arr) {
    vector<int> ret(arr, arr+N);
    int mi = *min_element(ret.begin(), ret.end()); mi--;
    for(int i = 0; i < N; i++) ret[i] -= mi;
    return ret;
}

pll dfs(int n, int x, vector<int> &cnt, vector<vector<int>> &E, vector<bool> &chk) {
    if(chk[x]) return {0LL, 0LL};
    chk[x] = true;
    pll ret = {0LL, cnt[x]};
    for(auto i : E[x]) {
        pll tmp = dfs(n, i, cnt, E, chk);
        ret = {(ret.fi+tmp.fi+tmp.se*(n-tmp.se))%P, (tmp.se+ret.se)%P};
    }
    //cout << x << "   " << ret << "\n";
    return ret;
}

int solve(int N, vector<int> X, vector<int> Y) {
    vector<vector<int>> P(101010);
    vector<vector<piii>> V(P.size());
    vector<int> cnt;
    for(int i = 0; i < N; i++) P[X[i]].push_back(Y[i]);
    for(int i = 0; i < P.size(); i++) {
        if(P[i].empty()) continue;
        sort(P[i].begin(), P[i].end());
        V[i].push_back({P[i][0], {0, cnt.size()}});
        for(int j = 1; j < P[i].size(); j++) {
            ++V[i].back().se.fi;
            if(P[i][j] > P[i][j-1]+1) {
                cnt.push_back(V[i].back().se.fi);
                V[i].push_back({P[i][j], {0, cnt.size()}});
            }
        }
        cnt.push_back(++V[i].back().se.fi);
    }
    //cout << cnt << " " << V;
    vector<vector<int>> E(cnt.size());
    for(int i = 1; i < P.size(); i++) {
        for(int j = 0, k = 0; j < P[i].size(); j++) {
            if(k+1 < V[i].size() && P[i][j] == V[i][k+1].fi) k++;
            piii tmp = {P[i][j], {INF, INF}};
            auto iter = upper_bound(V[i-1].begin(), V[i-1].end(), tmp);
            if(iter == V[i-1].begin()) continue;
            int x = V[i][k].se.se, y = (--iter)->se.se;
            if(iter->fi+iter->se.fi <= P[i][j]) continue;
            if(E[x].empty() || E[x].back() != y) {
                E[x].push_back(y);
                E[y].push_back(x);
            }
        }
    }
    //cout << " " << E;
    vector<bool> chk(cnt.size(), false);
    pll ret = dfs(N, 0, cnt, E, chk);
    //cout << ret.fi << "\n";
    return ret.fi;
}

int DistanceSum(int N, int *X, int *Y) {
    vector<int> A = compact(N, X), B = compact(N, Y);
    int xx = solve(N, A, B), yy = solve(N, B, A);
    return (xx+yy)%P;
}

Compilation message

city.cpp: In function 'int solve(int, std::vector<int>, std::vector<int>)':
city.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i = 0; i < P.size(); i++) {
      |                    ~~^~~~~~~~~~
city.cpp:47:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for(int j = 1; j < P[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~
city.cpp:58:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i = 1; i < P.size(); i++) {
      |                    ~~^~~~~~~~~~
city.cpp:59:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(int j = 0, k = 0; j < P[i].size(); j++) {
      |                               ~~^~~~~~~~~~~~~
city.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |             if(k+1 < V[i].size() && P[i][j] == V[i][k+1].fi) k++;
      |                ~~~~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4948 KB Output is correct
2 Correct 5 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 5 ms 4948 KB Output is correct
5 Correct 5 ms 5076 KB Output is correct
6 Correct 5 ms 4988 KB Output is correct
7 Correct 5 ms 5076 KB Output is correct
8 Correct 5 ms 5048 KB Output is correct
9 Correct 5 ms 5076 KB Output is correct
10 Correct 5 ms 5076 KB Output is correct
11 Correct 5 ms 5076 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5076 KB Output is correct
2 Correct 5 ms 5044 KB Output is correct
3 Correct 5 ms 5076 KB Output is correct
4 Correct 6 ms 5052 KB Output is correct
5 Correct 7 ms 5204 KB Output is correct
6 Correct 7 ms 5100 KB Output is correct
7 Correct 5 ms 5204 KB Output is correct
8 Correct 5 ms 5076 KB Output is correct
9 Correct 5 ms 5052 KB Output is correct
10 Correct 6 ms 5084 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5740 KB Output is correct
2 Correct 10 ms 5752 KB Output is correct
3 Correct 20 ms 6624 KB Output is correct
4 Correct 20 ms 6648 KB Output is correct
5 Correct 32 ms 8272 KB Output is correct
6 Correct 30 ms 8352 KB Output is correct
7 Correct 32 ms 8364 KB Output is correct
8 Correct 34 ms 8260 KB Output is correct
9 Correct 32 ms 8460 KB Output is correct
10 Correct 46 ms 14212 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6356 KB Output is correct
2 Correct 13 ms 6404 KB Output is correct
3 Correct 29 ms 8540 KB Output is correct
4 Correct 24 ms 8040 KB Output is correct
5 Correct 53 ms 12008 KB Output is correct
6 Correct 41 ms 10248 KB Output is correct
7 Correct 50 ms 12276 KB Output is correct
8 Correct 42 ms 10316 KB Output is correct
9 Correct 39 ms 9836 KB Output is correct
10 Correct 38 ms 9720 KB Output is correct