Submission #868884

#	Time	Username	Problem	Language	Result	Execution time	Memory
868884		HuyQuang_re_Zero	Ideal city (IOI12_city)	C++14	100 / 100	109 ms	18056 KiB

city

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define N 100005
using namespace std;
struct pt { int x,y,pos; } a[N];
struct International_Olympiad_in_Informatics
{
    vector <int> a[N];
    ll n,i,j,step,u,v,mod=1e9,sz[N],res,node[N];
    void DFS(int u,int p)
    {
        for(int v:a[u])
            if(v!=p)
            {
                DFS(v,u);
                sz[u]+=sz[v];
                res=(res+sz[v]*(n-sz[v]))%mod;
            }
    }
    int Work(int _n,pt cell[])
    {
        n=_n;
        res=0;
        for(step=0;step<=1;step++)
        {
            map <II,int> num;
            memset(sz,0,sizeof(sz));
            sort(cell+1,cell+n+1,[&](pt a,pt b){ return (a.x<b.x || (a.x==b.x && a.y<b.y)); });
            for(i=1;i<=n;i++)
            {
                num[make_pair(cell[i].x,cell[i].y)]=i;
                a[i].clear();
            }
            int u=1;
            for(i=1;i<=n;i++)
            {
                node[i]=u;
                if(i==n || cell[i+1].x>cell[i].x || (cell[i+1].x==cell[i].x && cell[i].y+1<cell[i+1].y))
                {
                    set <int> s;
                    for(j=i;node[j]==u;j--)
                    {
                        s.insert(node[num[make_pair(cell[j].x-1,cell[j].y)]]);
                        sz[u]++;
                    }
                    for(int v:s)
                        if(v>0)
                        {
                            a[u].push_back(v),a[v].push_back(u);
                        }
                    u++;
                }
            }
            DFS(1,0);

            for(i=1;i<=n;i++) swap(cell[i].x,cell[i].y);
        }
        return res;
    }
} IOI;

int x[N],y[N],n,i;

int DistanceSum(int n,int _x[], int _y[])
{
    for(int i=n;i>=1;i--) a[i].x=_x[i-1],a[i].y=_y[i-1];
    return IOI.Work(n,a);
}
/*
int main()
{
    freopen("city.inp","r",stdin);
    freopen("city.out","w",stdout);
    cin>>n;
    for(i=0;i<n;i++) cin>>x[i]>>y[i];
    cout<<DistanceSum(n,x,y);
}
*/

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