Submission #16752

#	Time	Username	Problem	Language	Result	Execution time	Memory
16752		CodingBug	Ideal city (IOI12_city)	C++98	100 / 100	69 ms	9456 KiB

city

#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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45