Submission #71169

#	Time	Username	Problem	Language	Result	Execution time	Memory
71169		MANcity	Ideal city (IOI12_city)	C++14	100 / 100	731 ms	56456 KiB

city

#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
const LL maMod=1000*1000*1000;
int N;
int X[200002];
int Y[200002];
vector<vector<int> > gh(100002);
vector<vector<int> > gv(100002);
int w_h[100002];
int w_v[100002];
pair<int,pair<int,int> > Sx[100002];
pair<int,pair<int,int> > Sy[100002];
int tree_h[100002];
int tree_v[100002];
int qan_h;
int qan_v;
map<pair<int,int>,int> map_h;
map<pair<int,int>,int> map_v;
map<pair<int,int>,int> kp_v;
map<pair<int,int>,int> kp_h;
void edge(int x,int y,int val)
{
    if(y==0 || x==0)
        return;
    if(x==y)
        return;
    if(val==2 && kp_v[{x,y}]==0 && kp_v[{y,x}]==0)
    {
        kp_v[{x,y}]=1;
        gv[x].push_back(y);
        gv[y].push_back(x);
    }
    if(val==1 && kp_h[{x,y}]==0 && kp_h[{y,x}]==0)
    {
        kp_h[{x,y}]=1;
        gh[x].push_back(y);
        gh[y].push_back(x);
    }
}
void connect(int x,int y,int val)
{
    int G=map_h[{x,y}];
    edge(G,map_h[{x-1,y}],1);
    edge(G,map_h[{x+1,y}],1);
    edge(G,map_h[{x,y-1}],1);
    edge(G,map_h[{x,y+1}],1);
    G=map_v[{x,y}];
    edge(G,map_v[{x-1,y}],2);
    edge(G,map_v[{x+1,y}],2);
    edge(G,map_v[{x,y-1}],2);
    edge(G,map_v[{x,y+1}],2);
}
LL SUM_H;
LL SUM_V;
LL vsum[1000002];
LL hsum[1000002];
LL ANS;
void dfs_h(int v,int p)
{
    for0(i,gh[v].size()-1)
    {
        int to=gh[v][i];
        if(to!=p)
        {
            dfs_h(to,v);
            hsum[v]=(hsum[v]+hsum[to])%maMod;
            ANS=((LL)ANS+(LL)(SUM_H-hsum[to])*(LL)hsum[to])%maMod;
        }
    }
    hsum[v]=(hsum[v]+w_h[v])%maMod;
}
void dfs_v(int v,int p)
{
    for0(i,gv[v].size()-1)
    {
        int to=gv[v][i];
        if(to!=p)
        {
            dfs_v(to,v);
            vsum[v]=(vsum[v]+vsum[to])%maMod;
            ANS=((LL)ANS+(LL)(SUM_V-vsum[to])*(LL)vsum[to])%maMod;
        }
    }
    vsum[v]=(vsum[v]+w_v[v])%maMod;
}
int DistanceSum(int N_0, int *X_0, int *Y_0) {
    N=N_0;
    for0(i,N-1)
        X[i]=X_0[i];
    for0(i,N-1)
        Y[i]=Y_0[i];
    for0(i,N-1)
        Sx[i]={X[i],{Y[i],i}};
    for0(i,N-1)
        Sy[i]={Y[i],{X[i],i}};
    Sx[N]={-1,{-1,-1}};

    sort(Sx,Sx+N+1);
    for1(i,N)
    {
        int x_now=Sx[i].first;
        int x_bef=Sx[i-1].first;
        int y_now=Sx[i].second.first;
        int y_bef=Sx[i-1].second.first;
        if(x_now!=x_bef || (y_now!=(y_bef+1)))
        {
            qan_v++;
        }
        w_v[qan_v]++;
        map_v[{x_now,y_now}]=qan_v;
        connect(x_now,y_now,2);
    }
    Sy[N]={-1,{-1,-1}};
    sort(Sy,Sy+N+1);
    for1(i,N)
    {
        int x_now=Sy[i].second.first;
        int x_bef=Sy[i-1].second.first;
        int y_now=Sy[i].first;
        int y_bef=Sy[i-1].first;
        if(y_now!=y_bef || (x_now!=(x_bef+1)))
        {
            qan_h++;
        }
         w_h[qan_h]++;
         map_h[{x_now,y_now}]=qan_h;
         connect(x_now,y_now,1);
    }
    for1(i,qan_h)
        SUM_H=(SUM_H+w_h[i])%maMod;
    for1(i,qan_v)
        SUM_V=(SUM_V+w_v[i])%maMod;
    dfs_h(1,0);
    dfs_v(1,0);
    return ANS;
}
/*
11
2 5
2 6
3 3
3 6
4 3
4 4
4 5
4 6
5 3
5 4
5 6
*/

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