Submission #1077858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077858		danikoynov	Golf (JOI17_golf)	C++14	30 / 100	3177 ms	782088 KiB

golf

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

struct Point
{
    int x, y;

    Point(int _x = 0, int _y = 0)
    {
        x = _x;
        y = _y;
    }

    void input()
    {
        cin >> x >> y;
    }
};

struct Rectangle
{
    Point A, B;

    Rectangle(Point _A = Point(), Point _B = Point())
    {
        A = _A;
        B = _B;
    }

    void input()
    {
        A.input();
        B.input();
    }
};

const int MAXN = 4010;

int n;
Rectangle rect[MAXN];
Point start, finish;
vector < pair < int, int > > adj[MAXN * MAXN];

void input()
{
  
    start.input();
    finish.input();  
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> rect[i].A.x >> rect[i].B.x;
        cin >> rect[i].A.y >> rect[i].B.y;
    }
}

map < pair < int, int >, int > idx;
pair < int, int > cross[MAXN * MAXN];

int m, fic;
set < int > sx, sy;

void create_edges_on_x(int x, vector < int > act)
{
    //cout << "create on x" << endl;
    //for (int y : act)
      //  cout << x << " : " << y << endl;
    fic ++;
    for (int y : act)
    {
        int id = idx[{x, y}];
        adj[id].push_back({fic, 0});
        adj[fic].push_back({id, 1});
    }
}


void create_edges_on_y(int y, vector < int > act)
{
    //cout << "create on y" << endl;
    //for (int x : act)
      //  cout << x << " : " << y << endl;
    fic ++;
    for (int x : act)
    {
        int id = idx[make_pair(x, y)];
        adj[id].push_back({fic, 0});
        adj[fic].push_back({id, 1});
    }
}

void build_graph() 
{

    for (int i = 1; i <= n; i ++)
    {
        sx.insert(rect[i].A.x);
        sx.insert(rect[i].B.x);
        sy.insert(rect[i].A.y);
        sy.insert(rect[i].B.y);
    }

    sx.insert(start.x);
    sx.insert(finish.x);
    sy.insert(start.y);
    sy.insert(finish.y);

    for (int x : sx)
        for (int y : sy)
        {
            cross[++ m] = {x, y};
            idx[make_pair(x, y)] = m;
            //cout << "cross " << x << " " << y << endl;
        }

    fic = m;
    for (int x : sx)
    {
        vector < pair < int, int > > events;
        for (int y : sy)
        {
            events.push_back({y, 1}); /// cross
        }
        for (int i = 1; i <= n; i ++)
        {
            if (rect[i].A.x < x && rect[i].B.x > x)
            {
                events.push_back({rect[i].A.y, 2});
                events.push_back({rect[i].B.y, 0});
            }
        }

        sort(events.begin(), events.end());
        vector < int > act;
        int fine = 1;
        for (pair < int, int > cur : events)
        {
            if (cur.second == 1)
            {
                if (fine == 1)
                    act.push_back(cur.first);
            }
            else
            if (cur.second == 2)
            {
                create_edges_on_x(x, act);
                act.clear();
                fine = 0;
            }
            else
            if (cur.second == 0)
            {
                fine = 1;
            }
        }

        create_edges_on_x(x, act);
    }

    for (int y : sy)
    {
        vector < pair < int, int > > events;
        for (int x : sx)
        {
            events.push_back({x, 1}); /// cross
        }
        for (int i = 1; i <= n; i ++)
        {
            if (rect[i].A.y < y && rect[i].B.y > y)
            {
                //cout << "ADD HERE ON " << y << endl;
                events.push_back({rect[i].A.x, 2});
                events.push_back({rect[i].B.x, 0});
            }
        }

        sort(events.begin(), events.end());
        vector < int > act;
        int fine = 1;
        for (pair < int, int > cur : events)
        {
            if (cur.second == 1)
            {
                if (fine == 1)
                    act.push_back(cur.first);
            }
            else
            if (cur.second == 2)
            {
                create_edges_on_y(y, act);
                act.clear();
                fine = 0;
            }
            else
            if (cur.second == 0)
            {
                fine = 1;
            }
        }

        create_edges_on_y(y, act);
    }
}

int used[MAXN * MAXN];
void bfs()
{
    deque < int > dq;
    for (int i = 1; i <= fic; i ++)
        used[i] = 1e9 + 10;
    used[idx[make_pair(start.x, start.y)]] = 0;
    dq.push_back(idx[make_pair(start.x, start.y)]);
    while(!dq.empty())
    {
        int v = dq.front();
        dq.pop_front();
        for (pair < int, int > nb : adj[v])
        {
            int u = nb.first, w = nb.second;
            if (used[u] > used[v] + w)
            {
                used[u] = used[v] + w;
                if (w == 0)
                    dq.push_front(u);
                else
                    dq.push_back(u);
            }
        }
    }

    cout << used[idx[make_pair(finish.x, finish.y)]] << endl;
}

void solve()
{
    input();
    build_graph();
    bfs();
}
int main()
{
    solve();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 70