Submission #151811

#	Time	Username	Problem	Language	Result	Execution time	Memory
151811		anonymous	Flood (IOI07_flood)	C++14	100 / 100	172 ms	12580 KiB

flood

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 3 / 3
• Subtask 5: 10 / 10
• Subtask 6: 3 / 3
• Subtask 7: 3 / 3
• Subtask 8: 3 / 3
• Subtask 9: 3 / 3
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9
• Subtask 13: 9 / 9
• Subtask 14: 9 / 9