oj.uz

Submission #54443

# Submission time Handle Problem Language Result Execution time Memory
54443 2018-07-03T12:57:50 Z SpaimaCarpatilor Flood (IOI07_flood) C++17
100 / 100
 302 ms 28188 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12156 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12264 KB Output is correct
2 Correct 12 ms 12320 KB Output is correct
3 Correct 12 ms 12320 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12320 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12320 KB Output is correct
2 Correct 12 ms 12428 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12476 KB Output is correct
2 Correct 12 ms 12476 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12476 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12476 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12476 KB Output is correct
2 Correct 12 ms 12476 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12476 KB Output is correct
2 Correct 12 ms 12476 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 14696 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 22228 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 22564 KB Output is correct
2 Correct 238 ms 27396 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 27396 KB Output is correct
2 Correct 247 ms 28188 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 28188 KB Output is correct
2 Correct 185 ms 28188 KB Output is correct