Submission #409508

#	Time	Username	Problem	Language	Result	Execution time	Memory
409508		definitelynotmee	Ideal city (IOI12_city)	C++98	100 / 100	250 ms	20732 KiB

city

#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 (stderr)

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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45