oj.uz

Submission #763791

# Submission time Handle Problem Language Result Execution time Memory
763791 2023-06-22T21:09:18 Z Username4132 Flood (IOI07_flood) C++14
45 / 100
 79 ms 9672 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{
    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

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

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

Subtask #2
10.0 / 10.0

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

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 1 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 Correct 2 ms 3412 KB Output is correct
2 Incorrect 2 ms 3412 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
3.0 / 3.0

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

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 4240 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 35 ms 6252 KB Output is correct

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 6232 KB Output is correct
2 Incorrect 79 ms 8424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

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

Subtask #14
0 / 9.0

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