oj.uz

Submission #763810

# Submission time Handle Problem Language Result Execution time Memory
763810 2023-06-22T22:20:38 Z Username4132 Flood (IOI07_flood) C++14
22 / 100
 69 ms 8340 KB 
#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

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

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

Subtask #2
0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 3.0

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

Subtask #5
0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
0 / 3.0

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

Subtask #8
0 / 3.0

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

Subtask #9
0 / 3.0

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

Subtask #10
0 / 9.0

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

Subtask #11
9.0 / 9.0

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

Subtask #12
0 / 9.0

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

Subtask #13
0 / 9.0

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

Subtask #14
0 / 9.0

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