Submission #630878

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
630878	2022-08-17T09:46:58 Z	sonamoo	Ideal city (IOI12_city)	C++14	Compilation error	0 ms	0 KB

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+1)/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

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:143:25: error: 'x' was not declared in this scope
  143 |         cell.push_back({x[i] , y[i]});
      |                         ^
city.cpp:143:32: error: 'y' was not declared in this scope
  143 |         cell.push_back({x[i] , y[i]});
      |                                ^
city.cpp:143:37: error: no matching function for call to 'std::vector<std::pair<int, int> >::push_back(<brace-enclosed initializer list>)'
  143 |         cell.push_back({x[i] , y[i]});
      |                                     ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from city.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, int>]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::pair<int, int>&'}
 1187 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, int>]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::pair<int, int> >::value_type&&' {aka 'std::pair<int, int>&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
city.cpp:144:38: error: no matching function for call to 'std::vector<std::pair<int, int> >::push_back(<brace-enclosed initializer list>)'
  144 |         cell2.push_back({y[i] , x[i]});
      |                                      ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from city.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, int>]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::pair<int, int>&'}
 1187 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, int>]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::pair<int, int> >::value_type&&' {aka 'std::pair<int, int>&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
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];
      |                     ~~^~~~~~~~~~~~~