oj.uz

Submission #71169

# Submission time Handle Problem Language Result Execution time Memory
71169 2018-08-24T07:38:54 Z MANcity Ideal city (IOI12_city) C++14
100 / 100
 731 ms 56456 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5112 KB Output is correct
2 Correct 7 ms 5136 KB Output is correct
3 Correct 8 ms 5184 KB Output is correct
4 Correct 7 ms 5228 KB Output is correct
5 Correct 9 ms 5288 KB Output is correct
6 Correct 8 ms 5292 KB Output is correct
7 Correct 8 ms 5292 KB Output is correct
8 Correct 9 ms 5416 KB Output is correct
9 Correct 9 ms 5416 KB Output is correct
10 Correct 8 ms 5416 KB Output is correct
11 Correct 7 ms 5416 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5708 KB Output is correct
2 Correct 12 ms 5708 KB Output is correct
3 Correct 14 ms 6012 KB Output is correct
4 Correct 13 ms 6012 KB Output is correct
5 Correct 15 ms 6200 KB Output is correct
6 Correct 13 ms 6200 KB Output is correct
7 Correct 16 ms 6356 KB Output is correct
8 Correct 14 ms 6356 KB Output is correct
9 Correct 14 ms 6356 KB Output is correct
10 Correct 15 ms 6356 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 9232 KB Output is correct
2 Correct 96 ms 9460 KB Output is correct
3 Correct 203 ms 14888 KB Output is correct
4 Correct 212 ms 15272 KB Output is correct
5 Correct 433 ms 24188 KB Output is correct
6 Correct 476 ms 25304 KB Output is correct
7 Correct 479 ms 27100 KB Output is correct
8 Correct 537 ms 27100 KB Output is correct
9 Correct 451 ms 28404 KB Output is correct
10 Correct 521 ms 43216 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 43216 KB Output is correct
2 Correct 91 ms 43216 KB Output is correct
3 Correct 322 ms 43216 KB Output is correct
4 Correct 276 ms 43216 KB Output is correct
5 Correct 728 ms 53964 KB Output is correct
6 Correct 520 ms 53964 KB Output is correct
7 Correct 731 ms 56456 KB Output is correct
8 Correct 604 ms 56456 KB Output is correct
9 Correct 609 ms 56456 KB Output is correct
10 Correct 536 ms 56456 KB Output is correct