Submission #770184

#	Time	Username	Problem	Language	Result	Execution time	Memory
770184		danikoynov	Walk (CEOI06_walk)	C++14	0 / 100	88 ms	22072 KiB

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 = 1000; /// 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;
    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;
                    if (ver <= n)
                    {

                        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;
}

Compilation message (stderr)

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:153:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |     for (int i = 0; i < events.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 100