oj.uz

답안 #307328

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
307328 2020-09-27T19:52:29 Z aZvezda 이상적인 도시 (IOI12_city) C++14
23 / 100
 288 ms 262144 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 ll MAX_N = 1e5 + 10;
vector<ll> g[MAX_N];
vector<pair<ll, pair<ll, ll> > > inter;
vector<pair<ll, ll> > grid;
ll n, ret = 0;

ll dfs(ll x, ll p) {
    ll sz = inter[x].second.second - inter[x].second.first + 1;
    for(auto it : g[x]) {
        if(it == p) {continue;}
        sz += dfs(it, x);
    }
    ret += sz * (n - sz);
    ret %= (1000000000ll);
    return sz;
}

void generateTree() {
    inter.resize(0);
    sort(grid.begin(), grid.end());
    for(ll i = 0; i < n; i ++) {
        ll 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(ll i = 0; i < inter.size(); i ++) {
        g[i].resize(0);
    }
    ll r = 0;
    for(ll l = 0; l < inter.size(); l ++) {
        while(r < inter.size() && inter[r].first == inter[l].first) {r ++;}
        if(r == inter.size()) {
            break;
        }
        while(r < n - 1 && inter[r].second.second < inter[l].second.first && inter[r + 1].first == inter[l].first + 1) {r ++;}
        while(r < n - 1 && inter[r].second.second <= inter[l].second.second && inter[r + 1].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(int 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(ll i = 0; i < n; i ++) {
        ll x, y;
        cin >> x >> y;
        grid.push_back({x, y});
    }

    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:41:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(ll i = 0; i < inter.size(); i ++) {
      |                   ~~^~~~~~~~~~~~~~
city.cpp:45:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(ll l = 0; l < inter.size(); l ++) {
      |                   ~~^~~~~~~~~~~~~~
city.cpp:46:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         while(r < inter.size() && inter[r].first == inter[l].first) {r ++;}
      |               ~~^~~~~~~~~~~~~~
city.cpp:47:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         if(r == inter.size()) {
      |            ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 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 Runtime error 288 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 242 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 3200 KB Output is correct
2 Correct 10 ms 3456 KB Output is correct
3 Correct 23 ms 4352 KB Output is correct
4 Correct 23 ms 4480 KB Output is correct
5 Correct 45 ms 5880 KB Output is correct
6 Correct 46 ms 6008 KB Output is correct
7 Correct 45 ms 6136 KB Output is correct
8 Correct 45 ms 5908 KB Output is correct
9 Correct 46 ms 6136 KB Output is correct
10 Correct 49 ms 9128 KB Output is correct

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 228 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -