Submission #101097

#	Time	Username	Problem	Language	Result	Execution time	Memory
101097		ansol4328	Ideal city (IOI12_city)	C++11	100 / 100	115 ms	14968 KiB

city

#include<vector>
#include<algorithm>

using namespace std;
typedef long long ll;

struct in
{
    ll x, y, Vn, Hn, vc, hc;
    in() {}
    in(ll a, ll b) : x(a), y(b) {}
};

bool cmp1(const in &a, const in &b)
{
    return a.x<b.x || (a.x==b.x && a.y<b.y);
}

bool cmp2(const in &a, const in &b)
{
    return a.y<b.y || (a.y==b.y && a.x<b.x);
}

ll n;
in m[100005];
ll Vcnt[100005], Hcnt[100005];
vector<ll> Vlst[100005], Hlst[100005];
ll res;
const ll MOD=1e9;

ll dfs(ll v, ll prev, vector<ll> *lst, ll *cnt)
{
    ll s=cnt[v];
    for(int i=0 ; i<lst[v].size() ; i++)
    {
        ll nxt=lst[v][i];
        if(nxt!=prev) s+=dfs(nxt,v,lst,cnt);
    }
    (res+=(n-s)*s)%=MOD;
    return s;
}

int DistanceSum(int N, int *X, int *Y)
{
	n=N;
    for(int i=1 ; i<=n ; i++) m[i].x=X[i-1], m[i].y=Y[i-1];
    //make vertical node
    sort(m+1,m+1+n,cmp1);
    ll ncnt=0;
    for(int i=1 ; i<=n ; i++)
    {
        if(m[i].x!=m[i-1].x || (m[i].x==m[i-1].x && m[i].y-m[i-1].y>1)) ncnt++;
        m[i].Vn=ncnt;
        Vcnt[ncnt]++;
        m[i].vc=Vcnt[ncnt];
    }
    //make horizontal node and vertical edge
    sort(m+1,m+1+n,cmp2);
    ncnt=0;
    for(int i=1 ; i<=n ; i++)
    {
        if(m[i].y!=m[i-1].y || (m[i].y==m[i-1].y && m[i].x-m[i-1].x>1)) ncnt++;
        m[i].Hn=ncnt;
        Hcnt[ncnt]++;
        m[i].hc=Hcnt[ncnt];
        if(m[i].y==m[i-1].y && m[i].x-m[i-1].x==1 && (m[i].vc==Vcnt[m[i].Vn] || m[i-1].vc==Vcnt[m[i-1].Vn]))
            Vlst[m[i].Vn].push_back(m[i-1].Vn), Vlst[m[i-1].Vn].push_back(m[i].Vn);
    }
    //make horizontal edge
    sort(m+1,m+1+n,cmp1);
    for(int i=1 ; i<=n ; i++)
    {
        if(m[i].x==m[i-1].x && m[i].y-m[i-1].y==1 && (m[i].hc==Hcnt[m[i].Hn] || m[i-1].hc==Hcnt[m[i-1].Hn]))
            Hlst[m[i].Hn].push_back(m[i-1].Hn), Hlst[m[i-1].Hn].push_back(m[i].Hn);
    }
    dfs(1,0,Vlst,Vcnt);
    dfs(1,0,Hlst,Hcnt);
    int ret=res;
    return ret;
}

Compilation message (stderr)

city.cpp: In function 'll dfs(ll, ll, std::vector<long long int>*, ll*)':
city.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0 ; i<lst[v].size() ; i++)
                   ~^~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45