Submission #763810

#	Time	Username	Problem	Language	Result	Execution time	Memory
763810		Username4132	Flood (IOI07_flood)	C++14	22 / 100	69 ms	8340 KiB

flood

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second

const int MAXN=100010;
int n, ans, w, used[2*MAXN];
bool marked[2*MAXN];
pii pt[MAXN];

struct wall{
    int ind, srcInd, dstInd;
    bool dir;
    wall(int Ind, int Src, int Dst, bool Dir) : ind(Ind), srcInd(Src), dstInd(Dst), dir(Dir) {}
};

struct edge{
    int nxt, eInd;
    edge(int Nxt=-1, int Eind=-1) : nxt(Nxt), eInd(Eind) {}
};

bool operator <(wall a, wall b){
    if(a.dir!=b.dir) return a.dir<b.dir;
    int ax = pt[a.srcInd].F, ay = pt[a.srcInd].S;
    int bx = pt[b.srcInd].F, by = pt[b.srcInd].S;
    return a.dir? ax<bx : ay<by;
}

edge g[MAXN][4];
vector<wall> remaining;

int main(){
    scanf("%d", &n);
    forn(i, n) scanf("%d %d", &pt[i].F, &pt[i].S);
    scanf("%d", &w);
    forn(i, w){
        int a, b; scanf("%d %d", &a, &b); --a, --b;
        if(pt[a].F == pt[b].F){
            if(pt[a].S > pt[b].S) swap(a, b);
            g[a][1] = edge(b, i);
            g[b][3] = edge(a, i);
            remaining.PB(wall(i, a, b, 1));
        }
        else{
            if(pt[a].F > pt[b].F) swap(a, b);
            g[a][0] = edge(b, i);
            g[b][2] = edge(a, i);
            remaining.PB(wall(i, a, b, 0));
        }
    }
    sort(remaining.begin(), remaining.end());
    while(!remaining.empty()){
        wall wl = remaining.back();
        remaining.pop_back();

        if(used[wl.ind]) continue;

        bool stop=false;
        int cur = wl.srcInd, fin = cur, fin2 = wl.dstInd, dir = (((int)wl.dir) + 3)&3;
        vector<int> toMark;
        while(true){ 
            int nd=(dir+1)&3, bck=(dir+2)&3;
            for(; (g[cur][nd].eInd==-1 || marked[g[cur][nd].eInd]) && nd!=bck; nd=(nd+3)&3);
            if(cur==fin && g[cur][nd].nxt==fin2 && stop) break;
            stop=true;

            toMark.PB(g[cur][nd].eInd);
            used[g[cur][nd].eInd]++;
            cur = g[cur][nd].nxt;
            dir = nd;
        }
        for(int mark:toMark) marked[mark]=true;
    }
    forn(i, w) if(used[i]>1) ++ans;
    printf("%d\n", ans);
    forn(i, w) if(used[i]>1) printf("%d\n", i+1);
}

Compilation message (stderr)

flood.cpp: In function 'int main()':
flood.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
flood.cpp:39:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     forn(i, n) scanf("%d %d", &pt[i].F, &pt[i].S);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d", &w);
      |     ~~~~~^~~~~~~~~~
flood.cpp:42:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         int a, b; scanf("%d %d", &a, &b); --a, --b;
      |                   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 3
• Subtask 5: 0 / 10
• Subtask 6: 3 / 3
• Subtask 7: 0 / 3
• Subtask 8: 0 / 3
• Subtask 9: 0 / 3
• Subtask 10: 0 / 9
• Subtask 11: 9 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9