Submission #163142

#	Time	Username	Problem	Language	Result	Execution time	Memory
163142		mhy908	Ideal city (IOI12_city)	C++14	100 / 100	65 ms	15060 KiB

city

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=987654321987654321;
const int inf=987654321;
int a, tx, ty, tmp, t, x[100010], y[100010];
LL sum, mod=1e9, sz[100010];
vector<int> grid[100002], edge[100010];
struct data{
    int num, s, e;
};
vector<data> T[100010];

void dfs(int r, int par){
    for(int k=0; k<edge[r].size(); k++){
        if(par==edge[r][k])continue;
        dfs(edge[r][k], r);
        sz[r]+=sz[edge[r][k]];
    }
    sum+=sz[r]*(LL)(a-sz[r]);
}
void func()
{
    t=0;
    for(int i=0; i<=a; i++)grid[i].clear(), T[i].clear(), edge[i].clear();
    for(int i=1; i<=a; i++)grid[x[i]].push_back(y[i]);
    for(int i=0; grid[i].size(); i++)sort(grid[i].begin(), grid[i].end());
    for(int i=0; grid[i].size(); i++){
        tmp=grid[i][0];
        for(int j=0; j<grid[i].size(); j++){
            if(j==grid[i].size()-1||grid[i][j]+1!=grid[i][j+1]){
                T[i].push_back({t++, tmp, grid[i][j]});
                sz[t-1]=grid[i][j]-tmp+1;
                if(j!=grid[i].size()-1)tmp=grid[i][j+1];
            }
        }
    }
    for(int i=1; T[i].size(); i++){
        int p=0, q=0;
        while(p<T[i-1].size()&&q<T[i].size()){
            if(!(T[i-1][p].e<T[i][q].s||T[i][q].e<T[i-1][p].s)){
                edge[T[i-1][p].num].push_back(T[i][q].num);
                edge[T[i][q].num].push_back(T[i-1][p].num);
            }
            if(T[i-1][p].e<T[i][q].e)p++;
            else q++;
        }
    }
    dfs(0, -1);
}
int DistanceSum(int N, int *X, int *Y)
{
    a=N;
    tx=inf;
    ty=inf;
    for(int i=1; i<=a; i++)x[i]=X[i-1], y[i]=Y[i-1];
    for(int i=1; i<=a; i++)tx=min(tx,x[i]), ty=min(ty,y[i]);
    for(int i=1; i<=a; i++)x[i]-=tx, y[i]-=ty;
    func();
    for(int i=1; i<=a; i++)t=x[i], x[i]=y[i], y[i]=t;
    func();
    return sum%mod;
}

Compilation message (stderr)

city.cpp: In function 'void dfs(int, int)':
city.cpp:22:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=0; k<edge[r].size(); k++){
                  ~^~~~~~~~~~~~~~~
city.cpp: In function 'void func()':
city.cpp:37:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<grid[i].size(); j++){
                      ~^~~~~~~~~~~~~~~
city.cpp:38:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(j==grid[i].size()-1||grid[i][j]+1!=grid[i][j+1]){
                ~^~~~~~~~~~~~~~~~~~
city.cpp:41:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(j!=grid[i].size()-1)tmp=grid[i][j+1];
                    ~^~~~~~~~~~~~~~~~~~
city.cpp:47:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(p<T[i-1].size()&&q<T[i].size()){
               ~^~~~~~~~~~~~~~
city.cpp:47:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(p<T[i-1].size()&&q<T[i].size()){
                                ~^~~~~~~~~~~~

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