oj.uz

Submission #16752

# Submission time Handle Problem Language Result Execution time Memory
16752 2015-09-18T05:33:09 Z CodingBug Ideal city (IOI12_city) C++
100 / 100
 69 ms 9456 KB 
#include <algorithm>
#include <stdio.h>
#include <vector>
#define M 100000
#define LMT 1000000000

using namespace std;

struct Node{
    int num;
    vector<Node *> con;
};

struct Invec{
    Node *no;
    pair<int,int> ivl;
    Invec(Node *_no=NULL,pair<int,int> _ivl=make_pair(0,0)):no(_no),ivl(_ivl){}
};

pair<int,int> a[M+1];
int n;

pair<int,int> findDist(Node *no,Node *p){
    int i;
    pair<int,int> ret=make_pair(0,no->num);

    for(i=0;i<no->con.size();i++){
        if(no->con[i]!=p){
            pair<int,int> k=findDist(no->con[i],no);
            ret.first=(ret.first+k.first)%LMT;
            ret.second+=k.second;
        }
    }
    ret.first+=((long long)ret.second*(n-ret.second))%LMT;
    ret.first%=LMT;
    return ret;
}

int DistSum(int N, int *X,int *Y){
    n=N;
    int i;

    for(i=0;i<N;i++) a[i]=make_pair(X[i],Y[i]);
    sort(a,a+N);

    vector<Invec> v[2];
    int l=0,p=0;

    Node *now=new Node();
    now->num=1;
    v[!l].push_back(Invec(now,make_pair(a[0].second,a[0].second)));

    for(i=1;i<N;i++){
        if(a[i-1].first==a[i].first){
            if(a[i-1].second+1==a[i].second){
                now->num++;
                v[!l].back().ivl.second++;
            }
            else{
                now=new Node();
                now->num=1;
                v[!l].push_back(Invec(now,make_pair(a[i].second,a[i].second)));
                p--;
                if(p<0) p=0;
            }
        }
        else{
            v[l].clear();
            p=0;
            l=!l;
            now=new Node();
            now->num=1;
            v[!l].push_back(Invec(now,make_pair(a[i].second,a[i].second)));
        }
        while(p<v[l].size() && v[l][p].ivl.second<a[i].second) p++;
        if(p<v[l].size() && v[l][p].ivl.first<=a[i].second && a[i].second<=v[l][p].ivl.second){
            now->con.push_back(v[l][p].no);
            v[l][p].no->con.push_back(now);
            p++;
        }
    }
    return findDist(now,NULL).first;
}

int DistanceSum(int N, int *X, int *Y) {
    return (DistSum(N,X,Y)+DistSum(N,Y,X))%LMT;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2196 KB Output is correct
2 Correct 10 ms 2328 KB Output is correct
3 Correct 24 ms 2512 KB Output is correct
4 Correct 29 ms 2512 KB Output is correct
5 Correct 49 ms 2904 KB Output is correct
6 Correct 48 ms 3036 KB Output is correct
7 Correct 46 ms 3168 KB Output is correct
8 Correct 35 ms 2904 KB Output is correct
9 Correct 45 ms 3112 KB Output is correct
10 Correct 55 ms 7124 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3516 KB Output is correct
2 Correct 13 ms 2988 KB Output is correct
3 Correct 31 ms 5680 KB Output is correct
4 Correct 31 ms 4360 KB Output is correct
5 Correct 69 ms 9240 KB Output is correct
6 Correct 60 ms 5416 KB Output is correct
7 Correct 68 ms 9456 KB Output is correct
8 Correct 57 ms 5456 KB Output is correct
9 Correct 46 ms 4884 KB Output is correct
10 Correct 50 ms 4620 KB Output is correct