제출 #291579

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
291579		Kastanda	Flood (IOI07_flood)	C++11	0 / 100	495 ms	65540 KiB

flood

// M
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 100005 * 2 * 2, MXK = 1e6 + 3;
int n, m, V[N], U[N], D[N], M[N];
pair < int , int > A[N];
vector < int > E[N], Events[MXK];
vector < pair < int , int > > Adj[N];
inline void AddEdge(int v, int u, int w)
{
        Adj[v].push_back({u, w});
        Adj[u].push_back({v, w});
}
int main()
{
        /* Main philosophy :
           Each edge has two sides, denoted by i*2-1 (left, down) and i*2 (right, up)
           */
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++)
                scanf("%d%d", &A[i].x, &A[i].y);
        scanf("%d", &m);
        for (int i = 1; i <= m; i ++)
        {
                scanf("%d%d", &V[i], &U[i]);
                E[V[i]].push_back(i);
                E[U[i]].push_back(i);
        }
        for (int i = 1; i <= n; i ++)
        {
                int l, r, d, u;
                l = r = d = u = 0;
                for (int e : E[i])
                {
                        int j = i ^ V[e] ^ U[e];
                        if (A[j].x < A[i].x)
                                l = e;
                        else if (A[j].x > A[i].x)
                                r = e;
                        else if (A[j].y < A[i].y)
                                d = e;
                        else
                                u = e;
                }

                // Now for the tedious casework :

                // 1. l with d and u
                if (l && d)
                        AddEdge(l * 2 - 1, d * 2 - 1, 0);
                if (l && u)
                        AddEdge(l * 2, u * 2 - 1, 0);

                // 2. r with d and u
                if (r && d)
                        AddEdge(r * 2 - 1, d * 2, 0);
                if (r && u)
                        AddEdge(r * 2, u * 2, 0);

                // 3. l with r
                if (l && r && !d)
                        AddEdge(l * 2 - 1, r * 2 - 1, 0);
                if (l && r && !u)
                        AddEdge(l * 2, r * 2, 0);

                // 4. d with u
                if (d && u && !l)
                        AddEdge(d * 2 - 1, u * 2 - 1, 0);
                if (d && u && !r)
                        AddEdge(d * 2, u * 2, 0);
        }

        for (int w = 0; w <= 1; w ++)
        {
                for (int i = 1; i <= m; i ++)
                        if (A[V[i]].x == A[U[i]].x)
                                Events[A[V[i]].x].push_back(i);

                set < pair < pair < int , int > , int > > ST;
                for (int i = 0; i < MXK; i ++)
                        for (int e : Events[i])
                        {
                                int ly = A[V[e]].y, ry = A[U[e]].y;
                                if (ly > ry) swap(ly, ry);
                                auto it = ST.lower_bound({{ly, -1}, -1});
                                if (it != ST.begin())
                                {
                                        it --;
                                        if (it->first.second > ly)
                                        {
                                                AddEdge(e * 2 - 1, it->second * 2, 0);
                                                auto TMp = * it;
                                                TMp.first.second = ly;
                                                it = ST.erase(it);
                                                ST.insert(TMp);
                                                it --;
                                                assert(* it == TMp);
                                        }
                                        it ++;
                                }
                                while (it != ST.end() && it->first.second <= ry)
                                        AddEdge(e * 2 - 1, it->second * 2, 0), it = ST.erase(it);
                                if (it != ST.end() && it->first.first < ry)
                                {
                                        AddEdge(e * 2 - 1, it->second * 2, 0);
                                        auto TMp = * it;
                                        TMp.first.first = ry;
                                        it = ST.erase(it);
                                        ST.insert(TMp);
                                        it --;
                                        assert(* it == TMp);
                                }
                                ST.insert({{ly, ry}, e});
                        }

                for (int i = 0; i < MXK; i ++)
                        Events[i].clear();
                for (int i = 1; i <= m; i ++)
                        swap(A[i].x, A[i].y);
        }

        for (int i = 1; i <= m; i ++)
                AddEdge(i * 2, i * 2 - 1, 1);

        deque < int > Dq;
        memset(D, 63, sizeof(D));
        for (int i = 1; i <= m * 2; i ++)
                if ((int)Adj[i].size() == 1)
                        D[i] = 0, Dq.push_back(i);

        while (Dq.size())
        {
                int v = Dq.front();
                Dq.pop_front();
                if (M[v])
                        continue;
                M[v] = 1;
                for (auto u : Adj[v])
                        if (D[u.x] > D[v] + u.y)
                        {
                                D[u.x] = D[v] + u.y;
                                if (!u.y) Dq.push_front(u.x);
                                else Dq.push_back(u.x);
                        }
        }

        vector < int > Rs;
        for (int i = 1; i <= m; i ++)
                if (D[i * 2] == D[i * 2 - 1])
                        Rs.push_back(i);

        printf("%d\n", (int)Rs.size());
        for (int i : Rs)
                printf("%d\n", i);
        return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

flood.cpp: In function 'int main()':
flood.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   21 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
flood.cpp:23:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |                 scanf("%d%d", &A[i].x, &A[i].y);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |         scanf("%d", &m);
      |         ~~~~~^~~~~~~~~~
flood.cpp:27:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |                 scanf("%d%d", &V[i], &U[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 3
• Subtask 5: 0 / 10
• Subtask 6: 0 / 3
• Subtask 7: 0 / 3
• Subtask 8: 0 / 3
• Subtask 9: 0 / 3
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9