oj.uz

답안 #766518

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
766518 2023-06-25T18:16:03 Z Username4132 Flood (IOI07_flood) C++14
0 / 100
 67 ms 11120 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 2388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 8044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 49 ms 8780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 63 ms 10280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 67 ms 11120 KB Output isn't correct
2 Halted 0 ms 0 KB -