oj.uz

Submission #1077858

# Submission time Handle Problem Language Result Execution time Memory
1077858 2024-08-27T09:49:12 Z danikoynov Golf (JOI17_golf) C++14
30 / 100
 3177 ms 782088 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 377940 KB Output is correct
2 Correct 151 ms 377900 KB Output is correct
3 Correct 155 ms 378000 KB Output is correct
4 Correct 170 ms 381524 KB Output is correct
5 Correct 583 ms 440644 KB Output is correct
6 Correct 568 ms 441432 KB Output is correct
7 Correct 540 ms 435512 KB Output is correct
8 Correct 545 ms 443224 KB Output is correct
9 Correct 535 ms 440352 KB Output is correct
10 Correct 577 ms 442036 KB Output is correct
11 Correct 627 ms 447068 KB Output is correct
12 Correct 517 ms 440056 KB Output is correct
13 Correct 541 ms 440752 KB Output is correct
14 Correct 610 ms 444752 KB Output is correct
15 Correct 306 ms 399956 KB Output is correct
16 Correct 927 ms 464992 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 377940 KB Output is correct
2 Correct 151 ms 377900 KB Output is correct
3 Correct 155 ms 378000 KB Output is correct
4 Correct 170 ms 381524 KB Output is correct
5 Correct 583 ms 440644 KB Output is correct
6 Correct 568 ms 441432 KB Output is correct
7 Correct 540 ms 435512 KB Output is correct
8 Correct 545 ms 443224 KB Output is correct
9 Correct 535 ms 440352 KB Output is correct
10 Correct 577 ms 442036 KB Output is correct
11 Correct 627 ms 447068 KB Output is correct
12 Correct 517 ms 440056 KB Output is correct
13 Correct 541 ms 440752 KB Output is correct
14 Correct 610 ms 444752 KB Output is correct
15 Correct 306 ms 399956 KB Output is correct
16 Correct 927 ms 464992 KB Output is correct
17 Correct 3177 ms 762912 KB Output is correct
18 Correct 3041 ms 762768 KB Output is correct
19 Correct 2744 ms 756908 KB Output is correct
20 Correct 2957 ms 761644 KB Output is correct
21 Correct 3102 ms 782088 KB Output is correct
22 Correct 2977 ms 774412 KB Output is correct
23 Correct 2966 ms 770900 KB Output is correct
24 Correct 2837 ms 767600 KB Output is correct
25 Correct 2844 ms 764296 KB Output is correct
26 Correct 2906 ms 765644 KB Output is correct
27 Correct 374 ms 409424 KB Output is correct
28 Correct 1000 ms 482940 KB Output is correct
29 Correct 935 ms 485716 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 377940 KB Output is correct
2 Correct 151 ms 377900 KB Output is correct
3 Correct 155 ms 378000 KB Output is correct
4 Correct 170 ms 381524 KB Output is correct
5 Correct 583 ms 440644 KB Output is correct
6 Correct 568 ms 441432 KB Output is correct
7 Correct 540 ms 435512 KB Output is correct
8 Correct 545 ms 443224 KB Output is correct
9 Correct 535 ms 440352 KB Output is correct
10 Correct 577 ms 442036 KB Output is correct
11 Correct 627 ms 447068 KB Output is correct
12 Correct 517 ms 440056 KB Output is correct
13 Correct 541 ms 440752 KB Output is correct
14 Correct 610 ms 444752 KB Output is correct
15 Correct 306 ms 399956 KB Output is correct
16 Correct 927 ms 464992 KB Output is correct
17 Correct 3177 ms 762912 KB Output is correct
18 Correct 3041 ms 762768 KB Output is correct
19 Correct 2744 ms 756908 KB Output is correct
20 Correct 2957 ms 761644 KB Output is correct
21 Correct 3102 ms 782088 KB Output is correct
22 Correct 2977 ms 774412 KB Output is correct
23 Correct 2966 ms 770900 KB Output is correct
24 Correct 2837 ms 767600 KB Output is correct
25 Correct 2844 ms 764296 KB Output is correct
26 Correct 2906 ms 765644 KB Output is correct
27 Correct 374 ms 409424 KB Output is correct
28 Correct 1000 ms 482940 KB Output is correct
29 Correct 935 ms 485716 KB Output is correct
30 Runtime error 376 ms 711504 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -