Submission #630880

#	Time	Username	Problem	Language	Result	Execution time	Memory
630880		sonamoo	Ideal city (IOI12_city)	C++14	23 / 100	1087 ms	11528 KiB

city

#include <bits/stdc++.h>
#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pii pair<int,int>
#define mod 1000000000
#define SIZE 100005

using namespace std;

int n;
vector<pii> cell , cell2;
long long int arr[SIZE] , sz[SIZE] , dp[SIZE] , pr[SIZE];
vector<int> graph[SIZE];
long long int ans;
long long int SUM;

bool cmp(pii A , pii B) {
    if (A.second == B.second) return A.first < B.first;
    return A.second < B.second;
}

void init() {
    memset(arr , 0 , sizeof(arr));
    memset(dp , 0 , sizeof(dp));
    memset(sz , 0 , sizeof(sz));
    for (int i = 0; i < SIZE; i++) graph[i].clear();
    SUM = 0;
}

void make_tree(int here) {
    for (auto there : graph[here]) {
        if (pr[there] == -1) {
            pr[there] = here;
            make_tree(there);
        }
    }
}

void solve(int here) {
    long long int res = 0;

    sz[here] = arr[here];
    for (auto there : graph[here]) {
        if (there  == pr[here]) continue;
        solve(there);
        sz[here] += sz[there];
    }

    ans += sz[here]*(SUM-sz[here]);
    ans %= mod;
}

void make_graph() {
    sort(cell.begin() , cell.end() , cmp);
   // cout << "=======\n";


    for (auto t : cell) {
        //cout << t.first << " " << t.second << "\n";
    }
    long long int s = cell[0].first;
    long long int e = cell[0].first;

    int siz = 0;
    vector<pair<int, pii> > tmp;
    vector<int> yidx;

    for (int i = 0; i < cell.size()-1; i++) {
        if (cell[i].second == cell[i+1].second && cell[i+1].first-cell[i].first == 1) e++;
        else {
            tmp.push_back({cell[i].second , {s , e}});
            arr[siz++] = e-s+1;
            yidx.push_back(cell[i].second);
            s = cell[i+1].first;
            e = cell[i+1].first;
        }
    }

    tmp.push_back({cell[cell.size()-1].second , {s , e}});
    arr[siz++] = e-s+1;
    yidx.push_back(cell[cell.size()-1].second);
    for (int i = 0; i < siz; i++) SUM += arr[i];
    //printf("ok1\n");

    sort(tmp.begin() , tmp.end());
    sort(yidx.begin() , yidx.end());
    yidx.push_back(1e18);

    for (int i = 0; i < tmp.size(); i++) {
        auto t = tmp[i];
       // cout << t.first << " " << t.second.first << " " << t.second.second << " : ";
       // cout << arr[i] << "\n";
    }

    for (int idx = 0; idx < tmp.size(); idx++) {
        int y = tmp[idx].first;
        int s = tmp[idx].second.first;
        int e = tmp[idx].second.second;

        int idx1 = lower_bound(yidx.begin() , yidx.end() , y+1)-yidx.begin();
        int idx2 = upper_bound(yidx.begin() , yidx.end() , y+1)-yidx.begin();
        idx2--;
        if (idx1 == yidx.size()-1) continue;

        int l = idx1;
        int r = idx2;
       // printf("ok1\n");
        while(l < r) {
            int mid = (l+r)/2;
            if (tmp[mid].second.second >= s) r = mid;
            else l = mid+1;
        }

        //printf("ok2\n");
        int lo = l;

        l = idx1;
        r = idx2;

        while(l < r) {
            int mid = (l+r)/2;
            //printf("%d %d %d\n" , l , r , mid);
            if (tmp[mid].second.first <= e) l = mid;
            else r = mid-1;
        }
      //  printf("ok3\n");

        int hi = l;
        for (int i = lo; i <= hi; i++) {
            graph[idx].push_back(i);
            graph[i].push_back(idx);
            //cout << idx << " " << i << "\n";
        }
    }

    memset(pr , -1 , sizeof(pr));
    pr[0] = 0;
    make_tree(0);
}

int DistanceSum(int N , int *X , int *Y) {
    n = N;
    for (int i = 0; i < n; i++) {
        cell.push_back({X[i] , Y[i]});
        cell2.push_back({Y[i] , X[i]});
    }
    make_graph();
    solve(0);
    ans %= mod;

    init();

    for (int i = 0; i < cell.size(); i++) cell[i] = cell2[i];
    make_graph();
    solve(0);
    ans %= mod;

    return ans;
}

Compilation message (stderr)

city.cpp: In function 'void solve(int)':
city.cpp:39:19: warning: unused variable 'res' [-Wunused-variable]
   39 |     long long int res = 0;
      |                   ^~~
city.cpp: In function 'void make_graph()':
city.cpp:57:15: warning: variable 't' set but not used [-Wunused-but-set-variable]
   57 |     for (auto t : cell) {
      |               ^
city.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < cell.size()-1; i++) {
      |                     ~~^~~~~~~~~~~~~~~
city.cpp:86:20: warning: overflow in conversion from 'double' to 'std::vector<int>::value_type' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   86 |     yidx.push_back(1e18);
      |                    ^~~~
city.cpp:88:23: 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]
   88 |     for (int i = 0; i < tmp.size(); i++) {
      |                     ~~^~~~~~~~~~~~
city.cpp:89:14: warning: variable 't' set but not used [-Wunused-but-set-variable]
   89 |         auto t = tmp[i];
      |              ^
city.cpp:94:27: 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]
   94 |     for (int idx = 0; idx < tmp.size(); idx++) {
      |                       ~~~~^~~~~~~~~~~~
city.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         if (idx1 == yidx.size()-1) continue;
      |             ~~~~~^~~~~~~~~~~~~~~~
city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:152:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |     for (int i = 0; i < cell.size(); i++) cell[i] = cell2[i];
      |                     ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 21
• Subtask 3: 23 / 23
• Subtask 4: 0 / 45