Submission #287393

#	Time	Username	Problem	Language	Result	Execution time	Memory
287393		stoyan_malinin	Ideal city (IOI12_city)	C++14	0 / 100	1085 ms	9196 KiB

city

//#include "grader.cpp"

#include <set>
#include <map>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

const int mod = 1e9;
const int MAXN = 1e5 + 5;

struct Point
{
    long long x, y;

    Point(){}
    Point(long long x, long long y)
    {
        this->x = x;
        this->y = y;
    }
};

long long getDist(Point A, Point B)
{
    return abs(A.x-B.x) + abs(A.y-B.y);
}

bool operator <(Point A, Point B)
{
    if(A.x!=B.x) return A.x<B.x;
    return A.y<B.y;
}

long long evalVector(vector <Point> v)
{
    long long answer = 0;

    sort(v.begin(), v.end(),
    [&](Point A, Point B)
    {
        if(A.x!=B.x) return A.x<B.x;
        return A.y<B.y;
    });

    long long sum = 0;
    for(int i = 0;i<v.size();i++)
    {
        answer = (answer + (i*1LL*v[i].x - sum))%mod;
        sum += v[i].x;
    }

    sort(v.begin(), v.end(),
    [&](Point A, Point B)
    {
        if(A.y!=B.y) return A.y<B.y;
        return A.x<B.x;
    });

    sum = 0;
    for(int i = 0;i<v.size();i++)
    {
        answer = (answer + (i*1LL*v[i].y - sum))%mod;
        sum += v[i].y;
    }

    return answer;
}

Point ind2Point[MAXN];
map <Point, int> point2Ind;

int cntOver[MAXN], depth[MAXN], treeSize[MAXN];
vector <int> graph[MAXN];

bool used[MAXN];
set <pair <int, int>> bridges;

long long answer = 0;
long long coef[MAXN];

void DFSInit(int x, int last, int level, int all)
{
    used[x] = true;
    depth[x] = level;

    cntOver[x] = 0;
    treeSize[x] = 1;
    for(int y: graph[x])
    {
        //if(x==9) cout << " ----> " << y << '\n';

        if(y==last) continue;
        if(used[y]==true)
        {
            if(depth[y]<depth[x]) cntOver[x]++;
            else cntOver[x]--;

            continue;
        }
        DFSInit(y, x, level+1, all);

        cntOver[x] += cntOver[y];
        treeSize[x] += treeSize[y];
    }

    //cout << x << " " << last << " -> " << treeSize[x] << " " << depth[x] << " || " << cntOver[x] << '\n';

    if(last!=-1 && cntOver[x]==0)
    {
        bridges.insert({x, last});
        bridges.insert({last, x});

        answer += treeSize[x]*1LL*(all-treeSize[x]);
        answer %= mod;

        //cout << x << " <=> " << last << " || " << treeSize[x] << " * " << all - treeSize[x] << '\n';
    }
}

void DFSNoBridge(int x, vector <int> &v)
{
    used[x] = true;
    v.push_back(x);

    for(int y: graph[x])
    {
        if(used[y]==true) continue;
        if(bridges.count({x, y})==true) continue;

        DFSNoBridge(y, v);
    }
}

void init(vector <Point> &v)
{
    set <Point>  s;
    for(int i = 0;i<v.size();i++)
    {
        s.insert(v[i]);

        ind2Point[i] = v[i];
        point2Ind[ v[i] ] = i;
    }

    for(int i = 0;i<v.size();i++)
    {
        for(pair <int, int> jump: vector <pair <int, int>>{{-1, 0}, {1, 0}, {0, -1}, {0, 1}})
        {
            Point a = v[i];
            Point b = Point(v[i].x+jump.first, v[i].y+jump.second);
            if(s.count(b)==false) continue;

            graph[ point2Ind[a] ].push_back(point2Ind[b]);
        }
    }

    //cout << "all bridges:" << '\n';
    DFSInit(0, -1, 1, v.size());
}

void doComponent(vector <int> &v)
{
    //if(v.size()>1) cout << "KKK" << '\n';
    for(int i: v)
    {
        for(int j: v)
        {
            if(i==j) continue;

            answer = (answer + coef[i]*getDist(ind2Point[i], ind2Point[j]))%mod;
            //cout << i << " -> " << coef[i] << " * " << getDist(ind2Point[i], ind2Point[j]) << '\n';
        }
    }

    for(int i: v)
    {
        for(int j: v)
        {
            if(i==j) continue;
            if(j>i) continue;

            answer = (answer + ((coef[i]*coef[j])%mod)*getDist(ind2Point[i], ind2Point[j]))%mod;
            //cout << i << " -> " << coef[i] << " * " << getDist(ind2Point[i], ind2Point[j]) << '\n';
        }
    }
}

void evalComponents(int n)
{
    memset(used, false, sizeof(used));
    for(int x = 0;x<n;x++)
    {
        if(used[x]==false)
        {
            vector <int> inds;
            DFSNoBridge(x, inds);

            vector <Point> v;
            for(int i: inds) v.push_back(ind2Point[i]);

            answer += evalVector(v);
            doComponent(inds);
        }
    }
}

void calcCoefs(int n)
{
    for(pair <int, int> e: bridges)
    {
        if(depth[e.first]>depth[e.second])
        {
            coef[e.first] += n - treeSize[e.first];
        }
        else
        {
            coef[e.first] += treeSize[e.second];
        }
    }

    //for(int i = 0;i<n;i++) cout << i << " -> " << coef[i] << '\n';
}

int DistanceSum(int N, int *X, int *Y)
{
    vector <Point> v;
    for(int i = 0;i<N;i++) v.push_back(Point(X[i], Y[i]));
    init(v);

    calcCoefs(N);
    evalComponents(N);

    return answer%mod;
}

Compilation message (stderr)

city.cpp: In function 'long long int evalVector(std::vector<Point>)':
city.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i = 0;i<v.size();i++)
      |                   ~^~~~~~~~~
city.cpp:66:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i = 0;i<v.size();i++)
      |                   ~^~~~~~~~~
city.cpp: In function 'void init(std::vector<Point>&)':
city.cpp:143:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     for(int i = 0;i<v.size();i++)
      |                   ~^~~~~~~~~
city.cpp:151:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |     for(int i = 0;i<v.size();i++)
      |                   ~^~~~~~~~~

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