Submission #291790

#	Time	Username	Problem	Language	Result	Execution time	Memory
291790		Kastanda	Flood (IOI07_flood)	C++11	100 / 100	334 ms	32624 KiB

flood

// M
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 100005, MXK = 1e6 + 3;
int n, m, V[N * 2], U[N * 2], D[N * 4];
bitset < N * 4 > M;
pair < int , int > A[N];
vector < int > E[N];
vector < int > Ad[N * 4];
inline void AddEdge(int v, int u)
{
        Ad[v].push_back(u);
        Ad[u].push_back(v);
}
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);
                if (l && u)
                        AddEdge(l * 2, u * 2 - 1);

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

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

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

                // Appendix :
                if (l && d && !r && !u)
                        AddEdge(l * 2, d * 2);
                if (l && u && !r && !d)
                        AddEdge(l * 2 - 1, u * 2);
                if (r && d && !l && !u)
                        AddEdge(r * 2, d * 2 - 1);
                if (r && u && !l && !d)
                        AddEdge(r * 2 - 1, u * 2 - 1);

                if (l && !r && !d && !u)
                        AddEdge(l * 2 - 1, l * 2);
                if (r && !l && !d && !u)
                        AddEdge(r * 2 - 1, r * 2);
                if (d && !l && !r && !u)
                        AddEdge(d * 2 - 1, d * 2);
                if (u && !l && !r && !d)
                        AddEdge(u * 2 - 1, u * 2);
        }

        vector < pair < int , int > > Events;
        for (int i = 1; i <= m; i ++)
                if (A[V[i]].x == A[U[i]].x)
                        Events.push_back({A[V[i]].x, i});
        sort(Events.begin(), Events.end());

        deque < int > Dq;
        memset(D, 63, sizeof(D));
        for (auto event : Events)
        {
                int e = event.second;
                if (M[e * 2 - 1])
                        continue;
                D[e * 2 - 1] = 0;
                Dq.push_back(e * 2 - 1);
                while (Dq.size())
                {
                        int v = Dq.front();
                        Dq.pop_front();
                        if (M[v])
                                continue;
                        M[v] = 1;
                        for (int u : Ad[v])
                                if (D[u] > D[v])
                                        D[u] = D[v], Dq.push_front(u);

                        int u;
                        if (v & 1) u = v + 1;
                        else u = v - 1;
                        if (D[u] > D[v] + 1)
                                D[u] = D[v] + 1, Dq.push_back(u);
                }
        }

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

Compilation message (stderr)

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

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