oj.uz

Submission #7679

# Submission time Handle Problem Language Result Execution time Memory
7679 2014-08-14T01:50:30 Z Namnamseo Ideal city (IOI12_city) C++
100 / 100
 228 ms 16936 KB 
#include <vector>
#include <algorithm>
#include <map>
#include <set>

using namespace std;

typedef pair<int,int> pp;

pp data[100010];

int ntonode[100010];
int nodesize[100010];
int treesize[100010];
bool visit[100010];
vector<int> edge[100010];

const int MODD=1000000000;

long long finalans;

int NNN;

void buildTree(int pos){
    visit[pos]=true;
    int i;
    int there;
    int n = edge[pos].size();
    for(i=0;i<n;i++){
        there = edge[pos][i];
        if(!visit[there]){
            buildTree(there);
            finalans = (finalans + 1LL*treesize[there]*(1LL*NNN-treesize[there]))%MODD;
            treesize[pos]+=treesize[edge[pos][i]];
        }
    }
    treesize[pos] += nodesize[pos];
}

int cutByX(int n,int *x,int *y) {
    finalans=0;
    set<pp> edgeset;
    int i;
    
    for(i=0;i<=100000;i++) {
        visit[i]=false;
        treesize[i]=nodesize[i]=ntonode[i]=0;
        edge[i].clear();
    }
    
    int nodeind=0;
    
    map<pp,int> mymap;
    map<pp,int>::iterator it;
    
    for(i=0;i<n;i++){
        mymap.insert(make_pair(make_pair(i[x],i[y]),0));
        data[i].first=x[i];
        data[i].second=y[i];
    }
    i=0;
    for(it=mymap.begin() ;it!=mymap.end(); it++){
        it->second = i;
        i++;
    }
    sort(data,data+n);
    
    for(i=0;i<n;i++){
        
        if(i==0 || data[i-1].first != data[i].first || 
           data[i-1].second+1 != data[i].second ) {
            nodeind++;
        }
        
        ntonode[i]=nodeind;
        nodesize[nodeind]++;
        
        it = mymap.find(make_pair(data[i].first-1, data[i].second));
        
        if(it != mymap.end()){
            edgeset.insert(make_pair(ntonode[it->second],nodeind));
        }
    }
    
    set<pp>::iterator it2;
    
    int a,b;
    
    for(it2=edgeset.begin(); it2!=edgeset.end(); it2++){
        a=it2->first; b=it2->second;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    
    buildTree(1);
    
    return finalans;
}

int DistanceSum(int n, int *x, int *y) {
    int i;
    NNN=n;
    int minx=2147483647;
    int miny=2147483647;
    for(i=0;i<n;i++){
        minx = min(minx, x[i]);
        miny = min(miny, y[i]);
    }
    for(i=0;i<n;i++){
        x[i]-=minx;
        y[i]-=miny;
    }
    return (cutByX(n,x,y)+cutByX(n,y,x))%MODD;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 7124 KB Output is correct
2 Correct 24 ms 7124 KB Output is correct
3 Correct 80 ms 9160 KB Output is correct
4 Correct 84 ms 9292 KB Output is correct
5 Correct 200 ms 12720 KB Output is correct
6 Correct 200 ms 12852 KB Output is correct
7 Correct 196 ms 12852 KB Output is correct
8 Correct 196 ms 12720 KB Output is correct
9 Correct 204 ms 13056 KB Output is correct
10 Correct 200 ms 16936 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 7652 KB Output is correct
2 Correct 36 ms 7388 KB Output is correct
3 Correct 100 ms 10744 KB Output is correct
4 Correct 96 ms 10096 KB Output is correct
5 Correct 228 ms 15756 KB Output is correct
6 Correct 220 ms 14024 KB Output is correct
7 Correct 224 ms 15984 KB Output is correct
8 Correct 212 ms 14080 KB Output is correct
9 Correct 212 ms 13644 KB Output is correct
10 Correct 208 ms 13512 KB Output is correct