oj.uz

Submission #304565

# Submission time Handle Problem Language Result Execution time Memory
304565 2020-09-21T14:10:09 Z Akashi Flood (IOI07_flood) C++14
32 / 100
 136 ms 10464 KB 
#include <bits/stdc++.h>
using namespace std;

const int DIM = 1e5 + 5;
const int NWALL = 2e5 + 5;

///Nord, Vest, Sud, Est
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};


int n, w;
int x[DIM], y[DIM];
pair <int, int> wh[DIM][4];
int cnt[NWALL];
bool viz[NWALL], touched[DIM];

struct elem {
    int a, b, id;
    bool operator < (const elem &aux) const{
        if (x[a] != x[aux.a]) return x[a] < x[aux.a];
        return y[a] > y[aux.a];
    }
};

int opus(int dir) {
    if (dir == 0 || dir == 2) dir = 2 - dir;
    else dir = 4 - dir;

    return dir;
}

void dfs(int nod, int dir, int root) {
    if (dir == 4) dir = 0;

    for (int d = dir + 1; d <= dir + 4 ; ++d) {
        int real = d;
        if (real >= 4) real -= 4;

        if (wh[nod][real].first == 0 || viz[wh[nod][real].second]) continue ;
        ++cnt[wh[nod][real].second];

        int aux = wh[nod][real].first;
        wh[nod][real].first = 0;

        if (aux != root)
        dfs(aux, opus(real), root);

        viz[wh[nod][real].second] = 1;
        break ;
    }
}

int main()
{
    #ifdef HOME
    freopen("flood.in", "r", stdin);
    freopen("flood.out", "w", stdout);
    #endif // HOME

    scanf("%d", &n);

    for (int i = 1; i <= n ; ++i)
        scanf("%d%d", &x[i], &y[i]);

    scanf("%d", &w);
    int a, b;

    vector <elem> wall;
    for (int i = 1; i <= w ; ++i) {
        scanf("%d%d", &a, &b);
        if (x[a] == x[b]) {
            if (y[a] > y[b]) swap(a, b);

            wh[a][0] = {b, i};
            wh[b][2] = {a, i};
        } else {
            if (x[a] > x[b]) swap(a, b);

            wh[a][3] = {b, i};
            wh[b][1] = {a, i};
        }

        wall.push_back({a, b, i});
    }

    sort (wall.begin(), wall.end());

    for (int i = 0; i < wall.size() ; ++i) {
        if (cnt[wall[i].id]) continue ;

        dfs(wall[i].a, 1, wall[i].a);
    }

    vector <int> sol;

    for (int i = 1; i <= wall.size() ; ++i)
        if (cnt[i] == 2) sol.push_back(i);

    printf("%d\n", sol.size());
    for (auto it : sol) printf("%d\n", it);

    return 0;
}

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<elem>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int i = 0; i < wall.size() ; ++i) {
      |                     ~~^~~~~~~~~~~~~
flood.cpp:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<elem>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (int i = 1; i <= wall.size() ; ++i)
      |                     ~~^~~~~~~~~~~~~~
flood.cpp:100:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  100 |     printf("%d\n", sol.size());
      |             ~^     ~~~~~~~~~~
      |              |             |
      |              int           std::vector<int>::size_type {aka long unsigned int}
      |             %ld
flood.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
flood.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |         scanf("%d%d", &x[i], &y[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
flood.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |     scanf("%d", &w);
      |     ~~~~~^~~~~~~~~~
flood.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |         scanf("%d%d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
3.0 / 3.0

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

Subtask #7
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 2428 KB Output isn't correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 8868 KB Output is correct

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 7788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 116 ms 9836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 136 ms 10464 KB Output isn't correct
2 Halted 0 ms 0 KB -