oj.uz

Submission #765500

# Submission time Handle Problem Language Result Execution time Memory
765500 2023-06-24T15:27:51 Z Username4132 Flood (IOI07_flood) C++14
73 / 100
 60 ms 8140 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1816 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 5776 KB Output is correct

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5880 KB Output is correct
2 Incorrect 59 ms 8140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 7436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 8044 KB Output isn't correct
2 Halted 0 ms 0 KB -