Submission #763789

#	Time	Username	Problem	Language	Result	Execution time	Memory
763789		Username4132	Flood (IOI07_flood)	C++14	45 / 100	140 ms	65536 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[MAXN];
pii pt[MAXN];

struct wall{
    bool dir;
    int len, ind, srcInd;
    wall(int Len, int Ind, int Src) : len(Len), ind(Ind), srcInd(Src) {}
};

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(pt[b].S - pt[a].S, i, a));
        }
        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(pt[b].F - pt[a].F, i, a));
        }
    }
    sort(remaining.begin(), remaining.end());
    while(!remaining.empty()){
        wall wl = remaining.back();
        remaining.pop_back();

        if(used[wl.ind]) continue;

        int cur = wl.srcInd, fin = cur, dir = ((int)wl.dir) + 1;
        vector<int> toMark;
        do{
            int nd=(dir+3)&3, bck=(dir+2)&3;
            for(; (g[cur][nd].eInd==-1 || marked[g[cur][nd].eInd]) && nd!=bck; nd=(nd+1)&3);
            toMark.PB(g[cur][nd].eInd);
            used[g[cur][nd].eInd]++;
            cur = g[cur][nd].nxt;
            dir = nd;
        } while(cur!=fin);
        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: 10 / 10
• Subtask 2: 10 / 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: 3 / 3
• Subtask 10: 0 / 9
• Subtask 11: 9 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9