제출 #280494

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
280494		eohomegrownapps	이상적인 도시 (IOI12_city)	C++14	100 / 100	106 ms	13612 KiB

city

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

ll cns = 1e9;

vector<vector<ll>> adjlist;
vector<ll> comsize;
ll comtot;

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

ll dfs(ll node, ll parent){
    ll ans = 0;
    for (ll 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<ll,ll>> &coords){
    ll curcom = 0;
    ll cursize = 0;
    vector<pair<ll,ll>> edgelist;
    adjlist.clear();
    comsize.clear();
    comtot = 0;
    unordered_map<ll,ll> 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 (ll 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<ll,ll>> coords(n);
    for (ll i = 0; i<n; i++){
        coords[i]={X[i],Y[i]};
    }

    sort(coords.begin(),coords.end(),[](pair<ll,ll> a, pair<ll,ll> b){return a.second==b.second?a.first<b.first:a.second<b.second;});
    ll tmpans = 0;
    tmpans+=getSum(coords);
    for (ll i = 0; i<n; i++){
        coords[i]={coords[i].second,coords[i].first};
    }
    sort(coords.begin(),coords.end(),[](pair<ll,ll> a, pair<ll,ll> 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: 23 / 23
• Subtask 4: 45 / 45