oj.uz

Submission #280493

# Submission time Handle Problem Language Result Execution time Memory
280493 2020-08-22T20:32:05 Z eohomegrownapps Ideal city (IOI12_city) C++14
32 / 100
 101 ms 9924 KB 
#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.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 1 ms 256 KB Output is correct
4 Correct 1 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 1 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 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1904 KB Output is correct
2 Correct 15 ms 2036 KB Output is correct
3 Correct 37 ms 4116 KB Output is correct
4 Correct 43 ms 4120 KB Output is correct
5 Incorrect 77 ms 7724 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2220 KB Output is correct
2 Correct 18 ms 2272 KB Output is correct
3 Correct 59 ms 5160 KB Output is correct
4 Correct 45 ms 4936 KB Output is correct
5 Incorrect 101 ms 9924 KB Output isn't correct
6 Halted 0 ms 0 KB -