oj.uz

Submission #288495

# Submission time Handle Problem Language Result Execution time Memory
288495 2020-09-01T14:26:10 Z stoyan_malinin Ideal city (IOI12_city) C++14
100 / 100
 317 ms 32844 KB 
//#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;
}

struct Tree
{
    int nodes = 0;
    map <Point, int> point2Node;

    vector <int> graph[MAXN];

    int allWeight = 0;
    int nodeWeight[MAXN];

    long long answer = 0;

    void addNode(vector <Point> &v)
    {
        nodes++;

        allWeight += v.size();
        nodeWeight[nodes] = v.size();

        for(Point p: v) point2Node[p] = nodes;
    }

    void addEdge(Point A, Point B)
    {
        if(point2Node.count(A)==false) return;
        if(point2Node.count(B)==false) return;

        int a = point2Node[A];
        int b = point2Node[B];
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    void normalize()
    {
        for(int x = 1;x<=nodes;x++)
        {
            sort(graph[x].begin(), graph[x].end());
            int newSz = unique(graph[x].begin(), graph[x].end()) - graph[x].begin();

            graph[x].resize(newSz);
        }
    }

    int dfs(int x, int last)
    {
        int treeWeight = nodeWeight[x];
        for(int y: graph[x])
        {
            if(y==last) continue;
            treeWeight += dfs(y, x);
        }

        if(last!=-1)
        {
            answer = (answer + treeWeight*1LL*(allWeight-treeWeight))%mod;
        }

        return treeWeight;
    }
};

Tree TH, TV;

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

    for(int i = 0;i<v.size();)
    {
        int y = v[i].y;
        vector <Point> currNode;

        for(;i<v.size();i++)
        {
            if(v[i].y!=y) break;

            if(currNode.empty()==true || currNode.back().x+1==v[i].x) currNode.push_back(v[i]);
            else
            {
                TV.addNode(currNode);
                for(Point p: currNode)
                {
                    Point other(p.x, p.y-1);
                    if(s.count(other)==true)
                    {
                        TV.addEdge(p, other);
                    }
                }

                currNode = {v[i]};
            }
        }

        TV.addNode(currNode);
        for(Point p: currNode)
        {
            Point other(p.x, p.y-1);
            if(s.count(other)==true)
            {
                TV.addEdge(p, other);
            }
        }
    }

    TV.normalize();
    TV.dfs(1, -1);
}

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

    for(int i = 0;i<v.size();)
    {
        int x = v[i].x;
        vector <Point> currNode;

        //cout << " ---- " << x << " --- " << '\n';

        for(;i<v.size();i++)
        {
            if(v[i].x!=x) break;

            if(currNode.empty()==true || currNode.back().y+1==v[i].y) currNode.push_back(v[i]);
            else
            {
                //cout << currNode.size() << '\n';

                TH.addNode(currNode);
                for(Point p: currNode)
                {
                    Point other(p.x-1, p.y);
                    if(s.count(other)==true)
                    {
                        TH.addEdge(p, other);
                    }
                }

                currNode = {v[i]};
            }
        }

        //cout << currNode.size() << '\n';

        TH.addNode(currNode);
        for(Point p: currNode)
        {
            Point other(p.x-1, p.y);
            if(s.count(other)==true)
            {
                TH.addEdge(p, other);
            }
        }
    }

    TH.normalize();
    TH.dfs(1, -1);
}

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

    buildVertical(v, s);
    //cout << TV.answer << '\n';

    buildHorizontal(v, s);
    //cout << TH.nodes << " " << TH.answer << '\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);

    return (TH.answer + TV.answer)%mod;
}
/*
4
0 0
0 1
1 0
1 1
*/

Compilation message

city.cpp: In function 'void buildVertical(std::vector<Point>, std::set<Point>&)':
city.cpp:113:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for(int i = 0;i<v.size();)
      |                   ~^~~~~~~~~
city.cpp:118:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for(;i<v.size();i++)
      |              ~^~~~~~~~~
city.cpp: In function 'void buildHorizontal(std::vector<Point>, std::set<Point>&)':
city.cpp:163:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     for(int i = 0;i<v.size();)
      |                   ~^~~~~~~~~
city.cpp:170:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |         for(;i<v.size();i++)
      |              ~^~~~~~~~~
city.cpp: In function 'void init(std::vector<Point>&)':
city.cpp:213:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  213 |     for(int i = 0;i<v.size();i++)
      |                   ~^~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 5 ms 5120 KB Output is correct
7 Correct 5 ms 5120 KB Output is correct
8 Correct 4 ms 5120 KB Output is correct
9 Correct 3 ms 5024 KB Output is correct
10 Correct 4 ms 5120 KB Output is correct
11 Correct 4 ms 5120 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5248 KB Output is correct
2 Correct 5 ms 5248 KB Output is correct
3 Correct 7 ms 5376 KB Output is correct
4 Correct 6 ms 5376 KB Output is correct
5 Correct 8 ms 5504 KB Output is correct
6 Correct 7 ms 5504 KB Output is correct
7 Correct 8 ms 5632 KB Output is correct
8 Correct 8 ms 5504 KB Output is correct
9 Correct 7 ms 5504 KB Output is correct
10 Correct 7 ms 5504 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 10256 KB Output is correct
2 Correct 49 ms 10288 KB Output is correct
3 Correct 137 ms 17976 KB Output is correct
4 Correct 125 ms 17888 KB Output is correct
5 Correct 304 ms 31088 KB Output is correct
6 Correct 284 ms 31056 KB Output is correct
7 Correct 262 ms 31056 KB Output is correct
8 Correct 282 ms 31300 KB Output is correct
9 Correct 271 ms 30544 KB Output is correct
10 Correct 272 ms 32844 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 10420 KB Output is correct
2 Correct 53 ms 10420 KB Output is correct
3 Correct 135 ms 18400 KB Output is correct
4 Correct 135 ms 18272 KB Output is correct
5 Correct 302 ms 31952 KB Output is correct
6 Correct 294 ms 31440 KB Output is correct
7 Correct 297 ms 31968 KB Output is correct
8 Correct 300 ms 31312 KB Output is correct
9 Correct 317 ms 31056 KB Output is correct
10 Correct 299 ms 31184 KB Output is correct