oj.uz

Submission #412986

# Submission time Handle Problem Language Result Execution time Memory
412986 2021-05-27T23:07:06 Z bigg Ideal city (IOI12_city) C++14
100 / 100
 174 ms 31320 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9;
const int MAXN = 3e5;
map<pair<int, int>, int > m[3];
ll ans = 0;
ll n;
vector<int> grafo[MAXN];

vector<pair<int, int> > v[3];
ll w[MAXN];
ll dfs(int x, int p){
    ll anslc =  w[x];
    for(int v: grafo[x]){
        if(v == p) continue;
      //  printf("%d %d\n", x, v);
        ll baixo = dfs(v,x);
        ans += baixo*(n-baixo); 
        ans%=MOD;
        anslc += baixo;
    }
    return anslc;
}
int naux;
int DistanceSum(int N, int *X, int *Y) {

    n = N;
   
    for(int aux = 0; aux < 2; aux++ ){
        int minx = (1<<30), manx = 0;
        int tam = -1;
        for(int i = 0; i < N; i++){
            if(aux) swap(X[i], Y[i]);
    
            minx = min(minx, X[i]), manx = max(manx, Y[i]);
            v[aux].push_back({X[i], Y[i]});
        }
        sort(v[aux].begin(), v[aux].end());
        int it1 = 0;
       // printf("%d\n", aux);
        while(it1 < v[aux].size()){
            int l = v[aux][it1].second;
            naux++;
            int r = v[aux][it1].second;
            set<int> jaachei;
            m[aux][{v[aux][it1].first, v[aux][it1].second}] = naux;
            if(m[aux][{v[aux][it1].first-1, v[aux][it1].second}]){
                jaachei.insert(m[aux][{v[aux][it1].first - 1, v[aux][it1].second}]);
                grafo[naux].push_back(m[aux][{v[aux][it1].first - 1, v[aux][it1].second}]);
                grafo[m[aux][{v[aux][it1].first - 1, v[aux][it1].second}]].push_back(naux);
            }
            while(it1 + 1 < v[aux].size() && v[aux][it1+1].first == v[aux][it1].first && v[aux][it1+1].second == v[aux][it1].second + 1){
                it1++;
                m[aux][{v[aux][it1].first, v[aux][it1].second}] = naux;
                r = v[aux][it1].second;
                if(m[aux][{v[aux][it1].first - 1, v[aux][it1].second}] && jaachei.find(m[aux][{v[aux][it1].first - 1, v[aux][it1].second}]) == jaachei.end()){
                    jaachei.insert(m[aux][{v[aux][it1].first - 1, v[aux][it1].second}]);
                    grafo[naux].push_back(m[aux][{v[aux][it1].first - 1, v[aux][it1].second}]);
                    grafo[m[aux][{v[aux][it1].first - 1, v[aux][it1].second}]].push_back(naux);
                }
            }
            w[naux] = r - l + 1;
           // printf("%d %d %d\n",r, l, naux);
            it1++;
        }
        dfs(naux,naux);
    }

    return ans;

}




// int main(){
//     int nn;
//     int x[400], y[400];
//     scanf("%d", &nn);
//     for(int i = 0; i < nn; i++){
//         scanf("%d %d", &x[i], &y[i]);
//     }
//     printf("%d\n", DistanceSum(nn, x, y));
// }

Compilation message

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         while(it1 < v[aux].size()){
      |               ~~~~^~~~~~~~~~~~~~~
city.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             while(it1 + 1 < v[aux].size() && v[aux][it1+1].first == v[aux][it1].first && v[aux][it1+1].second == v[aux][it1].second + 1){
      |                   ~~~~~~~~^~~~~~~~~~~~~~~
city.cpp:32:13: warning: unused variable 'tam' [-Wunused-variable]
   32 |         int tam = -1;
      |             ^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 6 ms 7328 KB Output is correct
3 Correct 4 ms 7244 KB Output is correct
4 Correct 5 ms 7264 KB Output is correct
5 Correct 4 ms 7244 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Correct 5 ms 7372 KB Output is correct
8 Correct 5 ms 7348 KB Output is correct
9 Correct 5 ms 7376 KB Output is correct
10 Correct 5 ms 7372 KB Output is correct
11 Correct 5 ms 7372 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7500 KB Output is correct
2 Correct 6 ms 7480 KB Output is correct
3 Correct 6 ms 7628 KB Output is correct
4 Correct 7 ms 7612 KB Output is correct
5 Correct 8 ms 7756 KB Output is correct
6 Correct 7 ms 7628 KB Output is correct
7 Correct 8 ms 7756 KB Output is correct
8 Correct 7 ms 7628 KB Output is correct
9 Correct 7 ms 7628 KB Output is correct
10 Correct 6 ms 7628 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 10424 KB Output is correct
2 Correct 25 ms 10560 KB Output is correct
3 Correct 60 ms 15232 KB Output is correct
4 Correct 61 ms 15304 KB Output is correct
5 Correct 125 ms 23156 KB Output is correct
6 Correct 118 ms 23224 KB Output is correct
7 Correct 115 ms 23620 KB Output is correct
8 Correct 125 ms 22968 KB Output is correct
9 Correct 123 ms 23520 KB Output is correct
10 Correct 153 ms 28168 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 11976 KB Output is correct
2 Correct 32 ms 11488 KB Output is correct
3 Correct 85 ms 19372 KB Output is correct
4 Correct 74 ms 17732 KB Output is correct
5 Correct 171 ms 31044 KB Output is correct
6 Correct 137 ms 26192 KB Output is correct
7 Correct 174 ms 31320 KB Output is correct
8 Correct 139 ms 26400 KB Output is correct
9 Correct 134 ms 25540 KB Output is correct
10 Correct 132 ms 25252 KB Output is correct