Submission #878931

#	Time	Username	Problem	Language	Result	Execution time	Memory
878931		YongXin	Ideal city (IOI12_city)	C++17	0 / 100	1071 ms	5212 KiB

city

#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
using namespace std;
int DistanceSum(int n,int*X,int*Y){
    ll x=0,y=0,maxx=0,maxy=0,minx=9e18,miny=9e18,r=0;
    vector<pll>vx,vy;
    queue<pll>q;
    pll a[n];
    for(ll i=0;i<n;++i){
        maxx=max(maxx,(ll)X[i]);
        maxy=max(maxy,(ll)Y[i]);
        minx=min(minx,(ll)X[i]);
        miny=min(miny,(ll)Y[i]);
    }
    sort(a,a+n);
    maxx-=minx-1;
    maxy-=miny-1;
    pll arr[maxy][maxx];
    memset(arr,-1,16*maxy*maxx);
    for(ll i=0;i<n;++i){
        X[i]-=minx;
        Y[i]-=miny;
        if(X[i]!=0&&arr[X[i]-1][Y[i]].first!=-1)a[i].first=arr[X[i]-1][Y[i]].first;
        else{
            a[i].first=x;
            ++x;
        }
        if(Y[i]!=0&&arr[X[i]][Y[i]-1].second!=-1)a[i].second=arr[X[i]][Y[i]-1].second;
        else{
            a[i].second=y;
            ++y;
        }
        arr[X[i]][Y[i]]=a[i];
        if(X[i]!=0&&arr[X[i]-1][Y[i]].first!=-1)vy.push_back(make_pair(arr[X[i]-1][Y[i]].second,a[i].second));
        if(Y[i]!=0&&arr[X[i]][Y[i]-1].second!=-1)vx.push_back(make_pair(arr[X[i]][Y[i]-1].first,a[i].first));
    }
    ll nx[x],ny[y];
    bool visitx[x],visity[y];
    vector<ll>adjx[x],adjy[y];
    memset(nx,0,8*x);
    memset(ny,0,8*x);
    for(ll i=0;i<n;++i){
        ++nx[a[i].first];
        ++ny[a[i].second];
    }
    sort(vx.begin(), vx.end());
    vx.erase(unique(vx.begin(),vx.end()),vx.end());
    sort(vy.begin(), vy.end());
    vy.erase(unique(vy.begin(),vy.end()),vy.end());
    for(ll i=0;i<vx.size();++i){
        adjx[vx[i].first].push_back(vx[i].second);
        adjx[vx[i].second].push_back(vx[i].first);
    }
    for(ll i=0;i<vy.size();++i){
        adjy[vy[i].first].push_back(vy[i].second);
        adjy[vy[i].second].push_back(vy[i].first);
    }
    for(ll i=0;i<x;++i){
        memset(visitx,-1,8*x);
        q.push(make_pair(i,1));
        while(!q.empty()){
            visitx[q.front().first]=false;
            for(ll j=0;j<adjx[q.front().first].size();++j)if(visitx[adjx[q.front().first][j]]){
                q.push(make_pair(adjx[q.front().first][j],q.front().second+1));
                r+=q.front().second*nx[i]*nx[adjx[q.front().first][j]];
            }
            q.pop();
        }
    }
    for(ll i=0;i<y;++i){
        memset(visity,-1,8*y);
        q.push(make_pair(i,1));
        while(!q.empty()){
            visity[q.front().first]=false;
            for(ll j=0;j<adjy[q.front().first].size();++j)if(visity[adjy[q.front().first][j]]){
                q.push(make_pair(adjy[q.front().first][j],q.front().second+1));
                r+=q.front().second*ny[i]*ny[adjy[q.front().first][j]];
            }
            q.pop();
        }
    }
    return (int)(r%(int)1e9);
}

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:51:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(ll i=0;i<vx.size();++i){
      |                ~^~~~~~~~~~
city.cpp:55:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(ll i=0;i<vy.size();++i){
      |                ~^~~~~~~~~~
city.cpp:64:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             for(ll j=0;j<adjx[q.front().first].size();++j)if(visitx[adjx[q.front().first][j]]){
      |                        ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
city.cpp:76:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             for(ll j=0;j<adjy[q.front().first].size();++j)if(visity[adjy[q.front().first][j]]){
      |                        ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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