Submission #54443

#	Time	Username	Problem	Language	Result	Execution time	Memory
54443		SpaimaCarpatilor	Flood (IOI07_flood)	C++17	100 / 100	302 ms	28188 KiB

flood

#include<bits/stdc++.h>

using namespace std;

int nr, N, M, x[100009], y[100009], a[400009], b[400009], nxt[400009], col[400009], d[400009], dir[400009], edg[100009][4];
bool ap[100009];
vector < int > h[100009], v[400009];

void read ()
{
    scanf ("%d", &N);
    for (int i=1; i<=N; i++)
        scanf ("%d %d", &x[i], &y[i]);
    scanf ("%d", &M);
    for (int i=1; i<=M; i++)
        scanf ("%d %d", &a[i], &b[i]),
        a[i + M] = b[i], b[i + M] = a[i],
        h[a[i]].push_back (i),
        h[b[i]].push_back (i + M);
    for (int i=1; i<=2 * M; i++)
    {
        if (y[a[i]] == y[b[i]]) dir[i] = 1 + 2 * (x[b[i]] < x[a[i]]);
        else dir[i] = 2 * (y[a[i]] > y[b[i]]);
        edg[a[i]][dir[i]] = i;
    }
}

void computeFaces ()
{
    for (int i=1; i<=2 * M; i++)
        for (int j=3; j<7; j++)
            if (edg[b[i]][(dir[i] + j) & 3])
            {
                nxt[i] = edg[b[i]][(dir[i] + j) & 3];
                break;
            }
    for (int i=1; i<=2 * M; i++)
        if (col[i] == 0)
        {
            int j = i; nr ++;
            while (col[j] == 0)
                col[j] = nr, j = nxt[j];
        }
}

void addEdge (int x, int y)
{
    v[x].push_back (y);
    v[y].push_back (x);
}

void buildGraph ()
{
    for (int i=1; i<=M; i++)
        if (col[i] != col[i + M])
            addEdge (col[i], col[i + M]);
}

vector < int > dfsComp;
void dfs (int nod)
{
    dfsComp.push_back (nod);
    ap[nod] = 1;
    for (auto it : h[nod])
        if (ap[a[it] ^ b[it] ^ nod] == 0)
            dfs (a[it] ^ b[it] ^ nod);
}

void startBfs (int source)
{
    queue < int > cc;
    cc.push (source), d[source] = 1;
    while (!cc.empty ())
    {
        int nod = cc.front ();
        cc.pop ();
        for (auto it : v[nod])
            if (d[it] == 0)
                d[it] = d[nod] + 1, cc.push (it);
    }
}

void computeDistances ()
{
    for (int i=1; i<=N; i++)
        if (ap[i] == 0)
        {
            dfsComp.clear ();
            dfs (i);
            int minE = -1, minX = 2e6 + 9, minY = 2e6 + 9;
            for (auto j : dfsComp)
                for (auto e : h[j])
                {
                    int l = a[e], r = b[e];
                    if (x[l] == x[r] && y[l] < y[r] && (x[l] < minX || (x[l] == minX && y[l] < minY)))
                        minX = x[l], minY = y[l], minE = e;
                }
            ///all this pain to find the outer level
            startBfs (col[minE]);
        }
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

read ();
computeFaces ();
buildGraph ();
computeDistances ();
/*for (int i=1; i<=2 * M; i++)
    printf ("(%2d %2d) %d %2d  (%2d %2d) %2d\n", a[i], b[i], dir[i], nxt[i], a[nxt[i]], b[nxt[i]], col[i]);
printf ("\n");*/
int cnt = 0;
for (int i=1; i<=M; i++)
    cnt += (d[col[i]] == d[col[i + M]]);
printf ("%d\n", cnt);
for (int i=1; i<=M; i++)
    if (d[col[i]] == d[col[i + M]])
        printf ("%d\n", i, a[i], b[i]);
return 0;
}

Compilation message (stderr)

flood.cpp: In function 'int main()':
flood.cpp:121:38: warning: too many arguments for format [-Wformat-extra-args]
         printf ("%d\n", i, a[i], b[i]);
                                      ^
flood.cpp: In function 'void read()':
flood.cpp:11:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &N);
     ~~~~~~^~~~~~~~~~
flood.cpp:13:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d %d", &x[i], &y[i]);
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:14:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &M);
     ~~~~~~^~~~~~~~~~
flood.cpp:18:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d %d", &a[i], &b[i]),
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
         a[i + M] = b[i], b[i + M] = a[i],
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
         h[a[i]].push_back (i),
         ~~~~~~~~~~~~~~~~~~~~~^~
         h[b[i]].push_back (i + M);
         ~~~~~~~~~~~~~~~~~~~~~~~~~

• 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