oj.uz

Submission #151811

# Submission time Handle Problem Language Result Execution time Memory
151811 2019-09-05T02:12:21 Z anonymous Flood (IOI07_flood) C++14
100 / 100
 172 ms 12580 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;
            
        } 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;
        }
        PQ.push({{-pt[wall[i][0]][0],-pt[wall[i][0]][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 376 KB Output is correct
2 Correct 3 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 3 ms 376 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 20 ms 2292 KB Output is correct

Subtask #11
9.0 / 9.0

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

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 7340 KB Output is correct
2 Correct 153 ms 9380 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 8816 KB Output is correct
2 Correct 172 ms 12580 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 9260 KB Output is correct
2 Correct 115 ms 10524 KB Output is correct