Submission #291592

#	Time	Username	Problem	Language	Result	Execution time	Memory
291592		Kastanda	Flood (IOI07_flood)	C++11	10 / 100	449 ms	65540 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], P[N];
bitset < N * 4 > M;
pair < int , int > A[N];
vector < int > E[N];
vector < int > Ad[N * 4];
int Find(int v)
{
        return (P[v] < 0 ? v : (P[v] = Find(P[v])));
}
inline void Merge(int v, int u)
{
        v = Find(v);
        u = Find(u);
        if (v != u)
                P[v] = u;
}
inline bool Connected(int v, int u)
{
        v = (v + 1) / 2;
        u = (u + 1) / 2;
        return Find(V[v]) == Find(V[u]);
}
inline void AddEdge(int v, int u)
{
        if (!Connected(v, u))
                return ;
        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)
           */
        memset(P, -1, sizeof(P));
        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);
                Merge(V[i], U[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);
        }

        for (int w = 0; w <= 1; w ++)
        {
                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());

                set < pair < pair < int , int > , int > > ST;
                for (auto event : Events)
                {
                        int e = event.second;
                        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);
                                        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), it = ST.erase(it);
                        if (it != ST.end() && it->first.first < ry)
                        {
                                AddEdge(e * 2 - 1, it->second * 2);
                                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 = 1; i <= m; i ++)
                        swap(A[i].x, A[i].y);
        }

        deque < int > Dq;
        memset(D, 63, sizeof(D));
        for (int i = 1; i <= m * 2; i ++)
                if ((int)Ad[i].size() == 0)
                        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 (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:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
flood.cpp:44:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |                 scanf("%d%d", &A[i].x, &A[i].y);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |         scanf("%d", &m);
      |         ~~~~~^~~~~~~~~~
flood.cpp:48:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |                 scanf("%d%d", &V[i], &U[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 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