oj.uz

Submission #109127

# Submission time Handle Problem Language Result Execution time Memory
109127 2019-05-04T14:57:40 Z PeppaPig Flood (IOI07_flood) C++14
100 / 100
 182 ms 8240 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+5;

int n, w, dir[N][4];
int X[N], Y[N], pos[N];
int A[N], B[N], chk[N][2];

int main() {
    iota(pos, pos+N, 0);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d %d", X+i, Y+i);
    scanf("%d", &w);
    for(int i = 1; i <= w; i++) {
        scanf("%d %d", A+i, B+i);
        if(X[A[i]] > X[B[i]] || Y[A[i]] > Y[B[i]]) swap(A[i], B[i]);
        if(X[A[i]] == X[B[i]]) dir[A[i]][2] = i, dir[B[i]][0] = i;
        else dir[A[i]][1] = i, dir[B[i]][3] = i;
    }
    sort(pos+1, pos+n+1, [&](const int &a, const int &b) {
        return make_pair(X[a], Y[a]) < make_pair(X[b], Y[b]);
    });
    for(int i = 1, idx; i <= n; i++) {
        while(1) {
            bool valid = false;
            int u = pos[i], d = 0;
            for(int j = 0; j < 4; j++) {
                int nex = dir[u][j];
                valid |= (nex && !chk[nex][j < 2]);
            }
            if(!valid) break;
            ++idx;
            vector<int> add;
            do {
                int nex, nd;
                for(int j = 0; j < 4; j++) {
                    nd = (d + j + 3) % 4;
                    nex = dir[u][nd]; 
                    if(nex && !chk[nex][nd < 2]) {
                        u = A[nex] + B[nex] - u, d = nd;
                        chk[nex][nd < 2] = idx;
                        add.emplace_back(nex);
                        break;
                    }
                }
            } while(u != pos[i]);
            for(int id : add) {
                if(!chk[id][0]) chk[id][0] = -1;
                if(!chk[id][1]) chk[id][1] = -1;
            }
        }
    }
    vector<int> ans;
    for(int i = 1; i <= w; i++) if(chk[i][0] == chk[i][1]) ans.emplace_back(i);
    printf("%d\n", (int)ans.size());
    for(int i : ans) printf("%d\n", i);

    return 0;
}

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
flood.cpp:14:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; i++) scanf("%d %d", X+i, Y+i);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~
flood.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &w);
     ~~~~~^~~~~~~~~~
flood.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", A+i, B+i);
         ~~~~~^~~~~~~~~~~~~~~~~~~
flood.cpp:34:13: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
             ++idx;
             ^~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1152 KB Output is correct
2 Correct 4 ms 1152 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1152 KB Output is correct
2 Correct 3 ms 1124 KB Output is correct

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1152 KB Output is correct
2 Correct 3 ms 1188 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1152 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct

Subtask #10
9.0 / 9.0

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

Subtask #11
9.0 / 9.0

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

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 6252 KB Output is correct
2 Correct 178 ms 7980 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 7540 KB Output is correct
2 Correct 182 ms 8240 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 7964 KB Output is correct
2 Correct 121 ms 8152 KB Output is correct