Submission #766518

#	Time	Username	Problem	Language	Result	Execution time	Memory
766518		Username4132	Flood (IOI07_flood)	C++14	0 / 100	67 ms	11120 KiB

flood

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using pii = pair<int, int>;
using ppi = pair<pii, 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, w, cou[2*MAXN];
bool ans[2*MAXN];
pii edges[2*MAXN], g[MAXN][4], pt[MAXN];
vector<ppi> remaining;
 
int getDir(int a, int b){
    pii pa = pt[a], pb = pt[b];
    if(pa.F == pb.F) return pa.S < pb.S? 1 : 3;
    else return pa.F < pb.F? 0 : 2;
}
 
int main(){
    scanf("%d", &n);
    forn(i, n) scanf("%d %d", &pt[i].F, &pt[i].S);
    forn(i, n) forn(j, 4) g[i][j] = {-1, -1};
    scanf("%d", &w);
    remaining.resize(w);
    forn(i, w){
        int a, b; scanf("%d %d", &a, &b); --a, --b;
        if(pt[a].F<pt[b].F) swap(a, b);
        edges[i]={a, b};
        remaining[i]={edges[i], i};
        g[a][getDir(a, b)] = {b, i};
        g[b][getDir(b, a)] = {a, i};
    }
    sort(remaining.begin(), remaining.end(), [](ppi a, ppi b){
        return pt[a.F.F].F < pt[b.F.F].F;
    });
 
    while(!remaining.empty()){
        ppi ed = remaining.back();
        remaining.pop_back();
 
        if(cou[ed.S]) continue;
 
        bool stop = false;
        int cur = ed.F.F, dir=2, ind, fin, finDir;
        vector<int> toClear;
        while(true){
            dir = (dir+3)&3;
            while(g[cur][dir].F==-1) dir = (dir+1)&3;
            ind = g[cur][dir].S;
            if(!stop) fin = ind, finDir = dir;
            if(ind==fin && finDir==dir && stop) break;
            stop = true;
            cur = g[cur][dir].F;
            toClear.PB(ind);
        }
        for(int e:toClear) cou[e]++;
        for(int e:toClear){
            int a = edges[e].F, b = edges[e].S;
            if(cou[e]>1){
                g[a][getDir(a, b)] = {-1, -1};
                g[b][getDir(b, a)] = {-1, -1};
            }
            else ans[e]=true;
        }
    }
 
    int total=0;
    forn(i, w) if(ans[i]) ++total;
    printf("%d\n", total);
    forn(i, w) if(ans[i]) printf("%d\n", i+1);
}

Compilation message (stderr)

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

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