oj.uz

Submission #725085

# Submission time Handle Problem Language Result Execution time Memory
725085 2023-04-16T20:16:58 Z stevancv Ideal city (IOI12_city) C++14
100 / 100
 138 ms 19200 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int inf = 1e9;
vector<int> g[N];
ll sz[N], ans;
void Dfs(int s, int e, int n) {
    for (int u : g[s]) {
        if (u == e) continue;
        Dfs(u, s, n);
        sz[s] += sz[u];
    }
    for (int u : g[s]) {
        if (u == e) continue;
        ans += sz[u] * (n - sz[u]);
    }
}
int Resi(int n, int x[], int y[]) {
    map<int, vector<int>> mp;
    map<pair<int, int>, int> id;
    for (int i = 0; i < n; i++) mp[x[i]].push_back(y[i]);
    for (int i = 0; i < n; i++) {
        g[i].clear();
        sz[i] = 0;
    }
    int tsz = 0;
    for (auto z : mp) {
        int ii = z.first;
        auto v = z.second;
        sort(v.begin(), v.end());
        int c = 0;
        for (int i = 0; i < v.size(); i++) {
            if (i == 0 || v[i - 1] + 1 == v[i]) c++;
            else {
                sz[tsz++] = c;
                c = 1;
            }
            id[{ii, v[i]}] = tsz;
        }
        sz[tsz++] = c;
        for (int i = 0; i < v.size(); i++) {
            if (id.find({ii - 1, v[i]}) != id.end()) {
                int o = id[{ii - 1, v[i]}];
                int oo = id[{ii, v[i]}];
                g[o].push_back(oo);
                g[oo].push_back(o);
            }
        }
    }
    for (int i = 0; i < tsz; i++) {
        sort(g[i].begin(), g[i].end());
        g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
    }
    ans = 0;
    Dfs(0, -1, n);
    ans %= inf;
    return ans;
}
int DistanceSum(int n, int x[], int y[]) {return (Resi(n, x, y) + Resi(n, y, x)) % inf;}

Compilation message

city.cpp: In function 'int Resi(int, int*, int*)':
city.cpp:38:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for (int i = 0; i < v.size(); i++) {
      |                         ~~^~~~~~~~~~
city.cpp:47:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (int i = 0; i < v.size(); i++) {
      |                         ~~^~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2660 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2656 KB Output is correct
7 Correct 2 ms 2656 KB Output is correct
8 Correct 2 ms 2664 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2660 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 3 ms 2772 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 3 ms 2900 KB Output is correct
6 Correct 4 ms 2924 KB Output is correct
7 Correct 4 ms 2900 KB Output is correct
8 Correct 3 ms 2900 KB Output is correct
9 Correct 4 ms 2772 KB Output is correct
10 Correct 4 ms 2800 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4836 KB Output is correct
2 Correct 22 ms 5120 KB Output is correct
3 Correct 56 ms 7980 KB Output is correct
4 Correct 55 ms 8380 KB Output is correct
5 Correct 117 ms 13512 KB Output is correct
6 Correct 118 ms 14328 KB Output is correct
7 Correct 117 ms 14256 KB Output is correct
8 Correct 115 ms 13228 KB Output is correct
9 Correct 108 ms 13924 KB Output is correct
10 Correct 138 ms 19200 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4944 KB Output is correct
2 Correct 22 ms 4992 KB Output is correct
3 Correct 60 ms 8276 KB Output is correct
4 Correct 58 ms 8420 KB Output is correct
5 Correct 118 ms 13912 KB Output is correct
6 Correct 120 ms 14080 KB Output is correct
7 Correct 113 ms 14032 KB Output is correct
8 Correct 117 ms 14040 KB Output is correct
9 Correct 114 ms 13652 KB Output is correct
10 Correct 128 ms 13844 KB Output is correct