oj.uz

Submission #307334

# Submission time Handle Problem Language Result Execution time Memory
307334 2020-09-27T21:28:31 Z aZvezda Ideal city (IOI12_city) C++14
100 / 100
 59 ms 7156 KB 
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
template<class T> inline void fix(T &x) {if(labs(x) >= mod) {x %= mod;} if(x < 0) {x += mod;}}
#define out(x) cout << __LINE__ << ": " << (#x) << " = " << (x) << endl
 
const int MAX_N = 1e5 + 10;
vector<int> g[MAX_N];
vector<pair<int, pair<int, int> > > inter;
vector<pair<int, int> > grid;
int n, ret = 0;
 
int dfs(int x, int p) {
    //cout << inter[x].first << " " << inter[x].second.first << " " << inter[x].second.second << endl;
    int sz = inter[x].second.second - inter[x].second.first + 1;
    for(auto it : g[x]) {
        if(it == p) {continue;}
        sz += dfs(it, x);
    }
    ret += ((ll)sz * (ll)(n - sz) % 1000000000ll);
    ret %= 1000000000ll;
    return sz;
}
 
void generateTree() {
    inter.resize(0);
    sort(grid.begin(), grid.end());
    for(int i = 0; i < n; i ++) {
        int j = i;
        while(j + 1 < n && grid[j + 1].first == grid[i].first && grid[j + 1].second == grid[j].second + 1) {j ++;}
        inter.push_back({grid[i].first, {grid[i].second, grid[j].second}});
        i = j;
    }
    for(int i = 0; i < inter.size(); i ++) {
        g[i].resize(0);
    }
    int r = 0;
    for(int l = 0; l < inter.size(); l ++) {
        while(r < inter.size() && inter[r].first < inter[l].first + 1) {r ++;}
        if(r == inter.size()) {
            break;
        }
        while(r < n - 1 && inter[r].second.second < inter[l].second.first && inter[r].first == inter[l].first + 1) {r ++;}
        while(r <= n - 1 && inter[r].second.second <= inter[l].second.second && inter[r].first == inter[l].first + 1) {
            g[l].push_back(r);
            g[r].push_back(l);
            r ++;
        }
        if(r != n && inter[r].second.first <= inter[l].second.second && inter[r].first == inter[l].first + 1) {
            g[l].push_back(r);
            g[r].push_back(l);
        }
    }
    dfs(0, -1);
}
 
 
int DistanceSum(int N, int *X, int *Y) {
    n = N;;
    grid.resize(n);
    for(ll i = 0; i < n; i ++) {
        grid[i] = {X[i], Y[i]};
    }
    generateTree();
    for(ll i = 0; i < n; i ++) {
        swap(grid[i].first, grid[i].second);
    }
    generateTree();
    return ret;
}
 
/*
signed main() {
    //ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for(int i = 0; i < n; i ++) {
        int x, y;
        cin >> x >> y;
        grid.push_back({x, y});
    }
    generateTree();
    for(int i = 0; i < n; i ++) {
        swap(grid[i].first, grid[i].second);
    }
    generateTree();
    cout << ret << endl;
    return 0;
}
*/
 
/*
11
2 5
2 6
3 3
3 6
4 3
4 4
4 5
4 6
5 3
5 4
5 6
*/

Compilation message

city.cpp: In function 'void generateTree()':
city.cpp:42:22: 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]
   42 |     for(int i = 0; i < inter.size(); i ++) {
      |                    ~~^~~~~~~~~~~~~~
city.cpp:46:22: 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]
   46 |     for(int l = 0; l < inter.size(); l ++) {
      |                    ~~^~~~~~~~~~~~~~
city.cpp:47:17: 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]
   47 |         while(r < inter.size() && inter[r].first < inter[l].first + 1) {r ++;}
      |               ~~^~~~~~~~~~~~~~
city.cpp:48:14: 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]
   48 |         if(r == inter.size()) {
      |            ~~^~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 3 ms 2688 KB Output is correct
9 Correct 3 ms 2688 KB Output is correct
10 Correct 3 ms 2688 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3072 KB Output is correct
2 Correct 10 ms 3104 KB Output is correct
3 Correct 22 ms 3584 KB Output is correct
4 Correct 24 ms 3584 KB Output is correct
5 Correct 43 ms 4344 KB Output is correct
6 Correct 44 ms 4472 KB Output is correct
7 Correct 44 ms 4476 KB Output is correct
8 Correct 46 ms 4472 KB Output is correct
9 Correct 44 ms 4600 KB Output is correct
10 Correct 47 ms 7156 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3456 KB Output is correct
2 Correct 11 ms 3456 KB Output is correct
3 Correct 29 ms 4860 KB Output is correct
4 Correct 27 ms 4568 KB Output is correct
5 Correct 56 ms 6896 KB Output is correct
6 Correct 50 ms 6072 KB Output is correct
7 Correct 59 ms 7024 KB Output is correct
8 Correct 49 ms 6076 KB Output is correct
9 Correct 48 ms 5688 KB Output is correct
10 Correct 47 ms 5560 KB Output is correct