oj.uz

Submission #1077856

# Submission time Handle Problem Language Result Execution time Memory
1077856 2024-08-27T09:48:33 Z danikoynov Golf (JOI17_golf) C++14
10 / 100
 2984 ms 917584 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 = 2010;

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 48 ms 95308 KB Output is correct
2 Correct 42 ms 95316 KB Output is correct
3 Correct 47 ms 95320 KB Output is correct
4 Correct 63 ms 98640 KB Output is correct
5 Correct 469 ms 158032 KB Output is correct
6 Correct 454 ms 158704 KB Output is correct
7 Correct 377 ms 152656 KB Output is correct
8 Correct 421 ms 160332 KB Output is correct
9 Correct 468 ms 157528 KB Output is correct
10 Correct 434 ms 159224 KB Output is correct
11 Correct 497 ms 164180 KB Output is correct
12 Correct 410 ms 157268 KB Output is correct
13 Correct 424 ms 158032 KB Output is correct
14 Correct 482 ms 162184 KB Output is correct
15 Correct 186 ms 117072 KB Output is correct
16 Correct 710 ms 182460 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 95308 KB Output is correct
2 Correct 42 ms 95316 KB Output is correct
3 Correct 47 ms 95320 KB Output is correct
4 Correct 63 ms 98640 KB Output is correct
5 Correct 469 ms 158032 KB Output is correct
6 Correct 454 ms 158704 KB Output is correct
7 Correct 377 ms 152656 KB Output is correct
8 Correct 421 ms 160332 KB Output is correct
9 Correct 468 ms 157528 KB Output is correct
10 Correct 434 ms 159224 KB Output is correct
11 Correct 497 ms 164180 KB Output is correct
12 Correct 410 ms 157268 KB Output is correct
13 Correct 424 ms 158032 KB Output is correct
14 Correct 482 ms 162184 KB Output is correct
15 Correct 186 ms 117072 KB Output is correct
16 Correct 710 ms 182460 KB Output is correct
17 Correct 2984 ms 480292 KB Output is correct
18 Correct 2944 ms 480084 KB Output is correct
19 Runtime error 2545 ms 917584 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 95308 KB Output is correct
2 Correct 42 ms 95316 KB Output is correct
3 Correct 47 ms 95320 KB Output is correct
4 Correct 63 ms 98640 KB Output is correct
5 Correct 469 ms 158032 KB Output is correct
6 Correct 454 ms 158704 KB Output is correct
7 Correct 377 ms 152656 KB Output is correct
8 Correct 421 ms 160332 KB Output is correct
9 Correct 468 ms 157528 KB Output is correct
10 Correct 434 ms 159224 KB Output is correct
11 Correct 497 ms 164180 KB Output is correct
12 Correct 410 ms 157268 KB Output is correct
13 Correct 424 ms 158032 KB Output is correct
14 Correct 482 ms 162184 KB Output is correct
15 Correct 186 ms 117072 KB Output is correct
16 Correct 710 ms 182460 KB Output is correct
17 Correct 2984 ms 480292 KB Output is correct
18 Correct 2944 ms 480084 KB Output is correct
19 Runtime error 2545 ms 917584 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -