답안 #54433 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54433	2018-07-03T12:17:52 Z	SpaimaCarpatilor	Flood (IOI07_flood)	C++17	0 / 100	2000 ms	27308 KB

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)
        {
            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\n", a[i], b[i], dir[i], nxt[i], col[i]);
printf ("\n");*/
for (int i=1; i<=M; i++)
    if (d[col[i]] == d[col[i + M]])
        printf ("%d\n", i);
return 0;
}

Compilation message

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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	11 ms	12156 KB	Output isn't correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	11 ms	12220 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	13 ms	12300 KB	Output isn't correct

Subtask #4
0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	12 ms	12300 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	11 ms	12324 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	11 ms	12348 KB	Output isn't correct

Subtask #7
0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	15 ms	12368 KB	Output isn't correct

Subtask #8
0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	12 ms	12392 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	13 ms	12392 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	363 ms	14912 KB	Output isn't correct

Subtask #11
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	2066 ms	22316 KB	Time limit exceeded

Subtask #12
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	2033 ms	22848 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #13
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	2056 ms	25712 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #14
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	2060 ms	27308 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-