oj.uz

Submission #696908

# Submission time Handle Problem Language Result Execution time Memory
696908 2023-02-07T15:21:27 Z whqkrtk04 Ideal city (IOI12_city) C++17
100 / 100
 58 ms 15656 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;
}

plll dfs(int x, vector<int> &cnt, vector<vector<int>> &E, vector<bool> &chk) {
    if(chk[x]) return {0LL, {0LL, 0LL}};
    chk[x] = true;
    plll ret = {0LL, {cnt[x], 0LL}};
    for(auto i : E[x]) {
        plll tmp = dfs(i, cnt, E, chk);
        ret = {(ret.fi+tmp.fi+(ret.se.fi*(tmp.se.fi+tmp.se.se))%P+ret.se.se*tmp.se.fi)%P,
                {(tmp.se.fi+ret.se.fi)%P, (tmp.se.se+ret.se.se+tmp.se.fi)%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);
    plll ret = dfs(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:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i = 0; i < P.size(); i++) {
      |                    ~~^~~~~~~~~~
city.cpp:49:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int j = 1; j < P[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~
city.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i = 1; i < P.size(); i++) {
      |                    ~~^~~~~~~~~~
city.cpp:61:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for(int j = 0, k = 0; j < P[i].size(); j++) {
      |                               ~~^~~~~~~~~~~~~
city.cpp:62: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]
   62 |             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 6 ms 4948 KB Output is correct
4 Correct 5 ms 4948 KB Output is correct
5 Correct 6 ms 4948 KB Output is correct
6 Correct 5 ms 5076 KB Output is correct
7 Correct 5 ms 5076 KB Output is correct
8 Correct 5 ms 4948 KB Output is correct
9 Correct 5 ms 4948 KB Output is correct
10 Correct 6 ms 4948 KB Output is correct
11 Correct 7 ms 5084 KB Output is correct

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5716 KB Output is correct
2 Correct 11 ms 5828 KB Output is correct
3 Correct 19 ms 6612 KB Output is correct
4 Correct 20 ms 6776 KB Output is correct
5 Correct 36 ms 8276 KB Output is correct
6 Correct 45 ms 8400 KB Output is correct
7 Correct 33 ms 8512 KB Output is correct
8 Correct 33 ms 8216 KB Output is correct
9 Correct 34 ms 8672 KB Output is correct
10 Correct 42 ms 15656 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6424 KB Output is correct
2 Correct 14 ms 6320 KB Output is correct
3 Correct 29 ms 8220 KB Output is correct
4 Correct 28 ms 7800 KB Output is correct
5 Correct 58 ms 11324 KB Output is correct
6 Correct 52 ms 9676 KB Output is correct
7 Correct 53 ms 11644 KB Output is correct
8 Correct 44 ms 9660 KB Output is correct
9 Correct 39 ms 9080 KB Output is correct
10 Correct 46 ms 8948 KB Output is correct