oj.uz

Submission #280494

# Submission time Handle Problem Language Result Execution time Memory
280494 2020-08-22T20:32:38 Z eohomegrownapps Ideal city (IOI12_city) C++14
100 / 100
 106 ms 13612 KB 
#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.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 3 ms 640 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2384 KB Output is correct
2 Correct 15 ms 2388 KB Output is correct
3 Correct 45 ms 5004 KB Output is correct
4 Correct 47 ms 5012 KB Output is correct
5 Correct 84 ms 9496 KB Output is correct
6 Correct 85 ms 10532 KB Output is correct
7 Correct 82 ms 10516 KB Output is correct
8 Correct 81 ms 10252 KB Output is correct
9 Correct 85 ms 10436 KB Output is correct
10 Correct 87 ms 13612 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2504 KB Output is correct
2 Correct 18 ms 2456 KB Output is correct
3 Correct 49 ms 5560 KB Output is correct
4 Correct 47 ms 5176 KB Output is correct
5 Correct 103 ms 10596 KB Output is correct
6 Correct 94 ms 10356 KB Output is correct
7 Correct 106 ms 11620 KB Output is correct
8 Correct 92 ms 10248 KB Output is correct
9 Correct 87 ms 9888 KB Output is correct
10 Correct 105 ms 9776 KB Output is correct