Submission #280493

#	Time	Username	Problem	Language	Result	Execution time	Memory
280493		eohomegrownapps	Ideal city (IOI12_city)	C++14	32 / 100	101 ms	9924 KiB

city

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll cns = 1e9;

vector<vector<int>> adjlist;
vector<int> comsize;
int comtot;

ll f(int a, int b){
    return a*cns+b;
}

ll dfs(int node, int parent){
    ll ans = 0;
    for (int i : adjlist[node]){
        if (i==parent){continue;}
        ans += dfs(i,node);
        ans += comsize[i]*(comtot-comsize[i]);
        comsize[node]+=comsize[i];
    }
    //cout<<comsize[node]<<endl;
    //cout<<node<<' '<<parent<<' '<<comsize[node]<<'\n';
    return ans;
}

ll getSum(vector<pair<int,int>> &coords){
    int curcom = 0;
    int cursize = 0;
    vector<pair<int,int>> edgelist;
    adjlist.clear();
    comsize.clear();
    comtot = 0;
    unordered_map<ll,int> visx;
    for (auto c : coords){
        if (cursize!=0&&visx.find(f(c.first-1,c.second))==visx.end()){
            comsize.push_back(cursize);
            comtot+=cursize;
            curcom++;
            cursize = 0;
        }
        cursize++;
        if (visx.find(f(c.first,c.second-1))!=visx.end()){
            edgelist.push_back({visx[f(c.first,c.second-1)],curcom});
            //cout<<visx[f(c.first,c.second-1)]<<' '<<curcom<<endl;
        }
        visx[f(c.first,c.second)]=curcom;
        //cout<<c.first<<' '<<c.second<<": "<<curcom<<endl;
    }
    comsize.push_back(cursize);
    comtot+=cursize;
    //cout<<comtot<<endl;
    /*for (int i : comsize){
        cout<<i<<' ';
    }cout<<endl;*/
    curcom++;
    sort(edgelist.begin(),edgelist.end());
    edgelist.erase(unique(edgelist.begin(),edgelist.end()),edgelist.end());
    adjlist.resize(curcom);
    assert(comsize.size()==adjlist.size());
    for (auto e : edgelist){
        adjlist[e.first].push_back(e.second);
        adjlist[e.second].push_back(e.first);
    }
    //cout<<"bleh"<<endl;
    return dfs(0,-1);
}

int DistanceSum(int n, int *X, int *Y) {
    vector<pair<int,int>> coords(n);
    for (int i = 0; i<n; i++){
        coords[i]={X[i],Y[i]};
    }

    sort(coords.begin(),coords.end(),[](pair<int,int> a, pair<int,int> b){return a.second==b.second?a.first<b.first:a.second<b.second;});
    ll tmpans = 0;
    tmpans+=getSum(coords);
    for (int i = 0; i<n; i++){
        coords[i]={coords[i].second,coords[i].first};
    }
    sort(coords.begin(),coords.end(),[](pair<int,int> a, pair<int,int> b){return a.second==b.second?a.first<b.first:a.second<b.second;});
    tmpans+=getSum(coords);
    return (tmpans)%1000000000;
}

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