Submission #770187

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
770187	2023-06-30T23:30:08 Z	danikoynov	Walk (CEOI06_walk)	C++14	0 / 100	108 ms	44580 KB

walk

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e5 + 10, maxc = 10000; /// fix this

struct point
{
    int x, y;

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

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

struct rectangle
{
    point A, B;

    void read()
    {
        A.read();
        B.read();
    }
} r[maxn];

struct line
{
    int x, y, len;
    int type;
    int idx;
    line(int _x, int _y, int _len, int _type, int _idx)
    {
        type = _type;
        x = _x;
        y = _y;
        len = _len;
        idx = _idx;
    }

    bool operator < (const line &l) const
    {
        if (x == l.x)
            return type > l.type;
        return x < l.x;
    }
};

int st_x, st_y, n;

void read()
{
    cin >> st_x >> st_y >> n;
    for (int i = 1; i <= n; i ++)
    {
        r[i].A.read();
        r[i].B.read();
        if (r[i].A.x > r[i].B.x)
            swap(r[i].A.x, r[i].B.x);
        if (r[i].B.y > r[i].B.y)
            swap(r[i].A.y, r[i].B.y);

        r[i].A.y += maxc;
        r[i].B.y += maxc;
    }
    st_y += maxc;
}


int sub[2 * maxn];
vector < int > adj[2 * maxn];
stack < int > st[maxc * 2];

int used[2 * maxn];
void dfs(int v)
{

    used[v] = 1;
    ///cout << v << " " << sub[v] << endl;

    if (adj[v].size() == 0)
        return;
    sub[v] = 1e9;

    for (int u : adj[v])
    {

        if (!used[u])
            dfs(u);

        int edge;
        int sx, sy, ex, ey;
        if (v == 0)
        {
            sx = 0;
            sy = maxc;
        }
        else if (v <= n)
        {
            sx = r[v].B.x;
            sy = r[v].A.y - 1;
        }
        else
        {
            sx = r[v - n].B.x;
            sy = r[v - n].B.y + 1;
        }

        if (u <= n)
        {
            ex = r[u].B.x;
            ey = r[u].A.y - 1;
        }
        else
        {
            ex = r[u - n].B.x;
            ey = r[u - n].B.y + 1;
        }

        edge = abs(sx - ex) + abs(sy - ey);
        ///cout << "edge " << v << " " << u << " " << edge << endl;
        ///cout << sx << " :: " << sy << " :: " << ex << "  " << ey << endl;
        sub[v] = min(sub[v], sub[u] + edge);
    }
    ///cout << v << " " << sub[v] << endl;
}
void sweep_line()
{
    vector < line > events;
    for (int i = 1; i <= n; i ++)
    {
        line l(r[i].A.x, r[i].A.y, r[i].B.y - r[i].A.y + 1, 1, i);
        events.push_back(l);
    }

    line sp(st_x, st_y, -1, 3, -1);
    events.push_back(sp);
    st[maxc].push(0);
    for (int i = 0; i < events.size(); i ++)
    {
        line l = events[i];
        if (l.type == 3)
        {
            for (int j = 0; j < 2 * maxc; j ++)
            {
                while(!st[j].empty())
                {

                    ///cout << ver << " ver " << sub[ver] << endl;
                    int ver = st[j].top();
                    st[j].pop();
                    int idx = ver;
                    if (idx > n)
                        idx -= n;
                        ///cout << "back " << ver << endl;
                    if (ver <= n)
                    {

                        if (ver == 0)
                            sub[ver] = st_x + abs(st_y - maxc);
                        else
                        sub[ver] = abs(r[ver].A.y - 1 - st_y) + abs(st_x - r[ver].B.x);
                        ///cout << "ver " << sub[ver] << " " << ver << endl;
                        ///cout << abs(r[ver].A.y - 1 - st_y) << endl;

                    }
                    else
                    {
                        sub[ver] = abs(r[ver - n].B.y + 1 - st_y) + abs(st_x - r[ver - n].B.x);
                    }
                }
            }
            break;
        }

        for (int j = l.y; j < l.y + l.len; j ++)
        {
            while(!st[j].empty())
            {
                ///cout << l.idx << endl;
                adj[st[j].top()].push_back(l.idx);
                adj[st[j].top()].push_back(l.idx + n);
                st[j].pop();
            }
        }
        ///cout << "here " << i << " " << l.idx << endl;
        st[l.y - 1].push(l.idx);
        st[l.y + l.len].push(l.idx + n);
    }

}

void solve()
{
    read();
    sweep_line();

    dfs(0);
    cout << sub[0] << endl;
}

int main()
{
    solve();
    return 0;
}
/**
4 2
1
1 -1
3 3
*/

Compilation message

walk.cpp: In function 'void read()':
walk.cpp:76:22: warning: self-comparison always evaluates to false [-Wtautological-compare]
   76 |         if (r[i].B.y > r[i].B.y)
      |             ~~~~~~~~ ^ ~~~~~~~~
walk.cpp: In function 'void sweep_line()':
walk.cpp:155:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     for (int i = 0; i < events.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	11 ms	20052 KB	Found length 121, official output says 89.
2	Incorrect	10 ms	20052 KB	Found length 1372, official output says 1190.
3	Runtime error	31 ms	40392 KB	Execution killed with signal 11
4	Runtime error	28 ms	40488 KB	Execution killed with signal 11
5	Runtime error	108 ms	43992 KB	Execution killed with signal 11
6	Runtime error	50 ms	41784 KB	Execution killed with signal 11
7	Runtime error	68 ms	42688 KB	Execution killed with signal 6
8	Runtime error	103 ms	44576 KB	Execution killed with signal 11
9	Runtime error	106 ms	44544 KB	Execution killed with signal 11
10	Runtime error	104 ms	44580 KB	Execution killed with signal 11