oj.uz

Submission #151810

# Submission time Handle Problem Language Result Execution time Memory
151810 2019-09-05T02:04:28 Z anonymous Flood (IOI07_flood) C++14
82 / 100
 130 ms 11380 KB 
#include<iostream>
#include<vector>
#include<queue>
#include<utility>
#define MAXN 100005
using namespace std;
int N,W,a,b,pt[MAXN][2],wall[2*MAXN][2],out;
int adj[MAXN][4][2], done[MAXN][4]; // N,E,S,W always prefer O-1 O O+1 O+2
vector <int> Edges_used;
bool del[2*MAXN],  checked[2*MAXN]; //has node blocked
priority_queue<pair<pair<int,int> ,int> > PQ;
void dfs(int u, int start, int O, bool first_call) { //start is edge that called the dfs
    if (first_call or u != start) {
        for (int j=O+3; j<O+7; j++) { //&3= mod 4
            int i=j&3;
            if (adj[u][i][0] and done[u][i] != start and !checked[adj[u][i][1]]) {
                Edges_used.push_back(adj[u][i][1]); //when going u->v edge is pushed by source
                done[u][i]=start;
                dfs(adj[u][i][0], start, i, false);
                return;
            }
        }
    }
}
int main() {
    //freopen("flood.in","r",stdin);
    //freopen("flood.out","w",stdout);
    scanf("%d",&N);
    for (int i=1; i<=N; i++) {
        scanf("%d %d",&pt[i][0],&pt[i][1]);
    }
    scanf("%d",&W);
    out=W;
    for (int i=1; i<=W; i++) {
        scanf("%d %d",&wall[i][0],&wall[i][1]);
        if (pt[wall[i][0]][0]>pt[wall[i][1]][0] or pt[wall[i][0]][1]>pt[wall[i][1]][1]) {
            swap(wall[i][0], wall[i][1]); //1 is higher x or y than 0
        }
        if (pt[wall[i][0]][0]==pt[wall[i][1]][0]) { //vertical edge
            adj[wall[i][0]][0][0]=wall[i][1];
            adj[wall[i][0]][0][1]=i;
            adj[wall[i][1]][2][0]=wall[i][0];
            adj[wall[i][1]][2][1]=i;
            PQ.push({{-pt[wall[i][0]][0],-pt[wall[i][0]][1]},i});
        } else { //horizontal
            adj[wall[i][0]][1][0]=wall[i][1];
            adj[wall[i][0]][1][1]=i;
            adj[wall[i][1]][3][0]=wall[i][0];
            adj[wall[i][1]][3][1]=i;
        }
    }
    while (PQ.size()) {
        while (PQ.size() and checked[PQ.top().second]) {PQ.pop();}
        if (PQ.empty()) {break;}
        int cur=PQ.top().second;
        PQ.pop();
        dfs(wall[cur][0],wall[cur][0],0,true);
        for (auto e: Edges_used) {
            out+=del[e] ? 1 : -1;
            del[e]=not(del[e]);
            checked[e]=true;
        }
        Edges_used.clear();
    }
    printf("%d\n",out);
    for (int i=1; i<=W; i++) {
        if (!del[i]) {printf("%d\n",i);}
    }
}

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
     ~~~~~^~~~~~~~~
flood.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&pt[i][0],&pt[i][1]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&W);
     ~~~~~^~~~~~~~~
flood.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&wall[i][0],&wall[i][1]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

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

Subtask #9
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

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

Subtask #11
9.0 / 9.0

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

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 9180 KB Output is correct
2 Incorrect 124 ms 11380 KB Output isn't correct

Subtask #13
0 / 9.0

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

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 11248 KB Output is correct
2 Correct 77 ms 8056 KB Output is correct