oj.uz

Submission #158312

# Submission time Handle Problem Language Result Execution time Memory
158312 2019-10-16T11:03:32 Z karma Flood (IOI07_flood) C++14
44 / 100
 622 ms 29916 KB 
#include<bits/stdc++.h>
#define FileName      "test"
#define ll            long long
#define pb            emplace_back
#define x             first
#define y             second
#define mp            make_pair

using namespace std;

typedef pair<int, int> pii;
const int N = int(2e5);

// Uu tien di: trai len phai xuong

pii e[N * 2], p[N];
int n, m, vis[N * 2];
vector<int> ans, a[N];
bool del[N * 2];
struct Less {
    bool operator()(const int& i, const int& j) {
        int u = e[i].x, v = e[j].x;
        if(p[u].y != p[v].y) return p[u].y < p[v].y;
        if(p[u].x != p[v].x) return p[u].x < p[v].x;
        return i < j;
    }
};
set<int, Less> edges;
queue<int> q;

pii operator -(const pii& a, const pii& b) {return mp(a.x - b.x, a.y - b.y);}
ll operator *(const pii& a, const pii& b) {return 1ll * a.x * b.y - 1ll * a.y * b.x;}

int Check(pii a, pii b, pii c) {
    ll t = (b - a) * (c - b);
    if(t == 0) {
      if(a.x == b.x && b.x == c.x) {
         if(a.y <= b.y && b.y <= c.y) return 1;
         if(a.y >= b.y && b.y >= c.y) return 1;
         return 3;
      }
      if(a.y == b.y && b.y == c.y) {
         if(a.x <= b.x && b.x <= c.x) return 1;
         if(a.x >= b.x && b.x >= c.x) return 1;
         return 3;
      }
    } else if(t < 0) return 0;
    else return 2;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if(fopen(FileName".inp", "r")) {
       freopen(FileName".inp", "r", stdin);
       freopen(FileName".out", "w", stdout);
    }
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> p[i].x >> p[i].y;
    cin >> m; m *= 2;
    for(int i = 0; i < m; i += 2) {
        cin >> e[i].x >> e[i].y;
        e[i ^ 1] = mp(e[i].y, e[i].x);
        a[e[i].x].pb(i), a[e[i].y].pb(i ^ 1);
        edges.insert(i), edges.insert(i ^ 1);
    }
    while(edges.size()) {
        int es = *edges.begin(), u = es;
        vector<int> edel;
        vis[es] = 1; q.push(es);
        while(q.size()) {
            es = q.front(), q.pop();
            edel.pb(es), edel.pb(es ^ 1);
            if(vis[es ^ 1]) ans.pb(es / 2 + 1);
            int ne = -1;
            for(int id: a[e[es].y])
                if((!vis[id] || id == u) && !del[id]) {
                  if(ne == -1) ne = id;
                  else
                    if(Check(p[e[es].x], p[e[es].y], p[e[id].y]) < Check(p[e[es].x], p[e[es].y], p[e[ne].y])) ne = id;
                }
            if(ne != -1 && !vis[ne]) vis[ne] = 1, q.push(ne);
        }
        for(int x: edel) del[x] = 1, edges.erase(x);
    }
    cout << ans.size() << '\n';
    for(int i: ans) cout << i << '\n';
}

Compilation message

flood.cpp: In function 'int Check(pii, pii, pii)':
flood.cpp:49:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
flood.cpp: In function 'int main()':
flood.cpp:55:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
        freopen(FileName".inp", "r", stdin);
        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:56:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
        freopen(FileName".out", "w", stdout);
        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 4988 KB Output is correct
3 Correct 7 ms 5112 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 3.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4984 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 6 ms 5112 KB Output is correct

Subtask #7
3.0 / 3.0

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

Subtask #8
0 / 3.0

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

Subtask #9
0 / 3.0

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

Subtask #10
9.0 / 9.0

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

Subtask #11
9.0 / 9.0

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

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 21568 KB Output is correct
2 Incorrect 622 ms 29916 KB Output isn't correct

Subtask #13
0 / 9.0

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

Subtask #14
0 / 9.0

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