oj.uz

Submission #409508

# Submission time Handle Problem Language Result Execution time Memory
409508 2021-05-21T01:58:57 Z definitelynotmee Ideal city (IOI12_city) C++
100 / 100
 250 ms 20732 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const int MOD = 1e9;
const int MAXN = 1e5+1;
 
set<pii> s;
int ct = -1;
map<pii, int> grupo;
vector<vector<pii>> lista;
vector<int> grafo[MAXN];
ll resp = 0;
int dfs(int id, int last, int n){
    int ret = lista[id].size();
    for(int i = 0; i < grafo[id].size(); i++){
        int viz= grafo[id][i];
        if(viz!=last){
            int ct = dfs(viz,id,n);
            resp+=(ll)ct*(n-ct);
            resp%=MOD;
            ret+=ct;
        }
    }
    return ret;
}
 
int DistanceSum(int N, int *X, int *Y){
    
    for(int k = 0; k < 2; k++){
        //cout << "it " << k << endl;
        ct=-1;
        s.clear();
        lista.clear();
        grupo.clear();
        int l = INF, r = -1;
        for(int i = 0; i < N; i++){
            grafo[i].clear();
            if(k==1)
                swap(X[i],Y[i]);
            s.insert({X[i],Y[i]});
            l = min(l,X[i]);
            r = max(r,X[i]);
        }
        auto it = s.begin();
        while(it!= s.end()){
            auto it2 = it;
            
            it2++;
            //cout << "(" << it->ff << ", " << it->ss << ") "  << "(" << it2->ff << ", " << it2->ss << ") "<< endl;
            lista.push_back({*it});
            grupo[*it] = ++ct;
            while(it2!=s.end() && it2->first == it->first && it2->second == it->second + 1){
                //cout << "->" << it2->ff << ' ' << it2->ss << '\n';
                grupo[*it2] = ct;
                lista[ct].push_back(*it2);
                it++;
                it2++;
            }
            it++;
        }
        /*for(int i = 0; i <= ct; i++){
            cout << i << " -> ";
            for(pii j : lista[i]){
                cout << "(" << j.ff << ", " << j.ss << ") ";
            }
            cout << '\n';
        }*/
        for(int i = 0; i <= ct; i++){
            set<int> temp;
            for(pii j : lista[i]){
                if(s.count({j.ff + 1, j.ss})){
                    int g = grupo[{j.ff+1,j.ss}];
                    if(!temp.count(g)){
                        //cout << "(" << j.ff << ", " << j.ss << ") <=> "<< "(" << j.ff+1 << ", " << j.ss << ") " << endl;
                        grafo[i].push_back(g);
                        grafo[g].push_back(i);
                        temp.insert(g);
                    }
                }
            }
        }
        dfs(0,-1,N);
    }
    return resp;
}

Compilation message

city.cpp: In function 'int dfs(int, int, int)':
city.cpp:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i = 0; i < grafo[id].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5560 KB Output is correct
2 Correct 34 ms 5452 KB Output is correct
3 Correct 86 ms 9548 KB Output is correct
4 Correct 97 ms 9448 KB Output is correct
5 Correct 237 ms 16672 KB Output is correct
6 Correct 223 ms 16580 KB Output is correct
7 Correct 199 ms 16668 KB Output is correct
8 Correct 241 ms 16452 KB Output is correct
9 Correct 201 ms 16528 KB Output is correct
10 Correct 240 ms 20732 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 6224 KB Output is correct
2 Correct 38 ms 5736 KB Output is correct
3 Correct 101 ms 10924 KB Output is correct
4 Correct 106 ms 10436 KB Output is correct
5 Correct 248 ms 19308 KB Output is correct
6 Correct 221 ms 17496 KB Output is correct
7 Correct 240 ms 19292 KB Output is correct
8 Correct 246 ms 17604 KB Output is correct
9 Correct 215 ms 17324 KB Output is correct
10 Correct 250 ms 17024 KB Output is correct