oj.uz

Submission #158322

# Submission time Handle Problem Language Result Execution time Memory
158322 2019-10-16T11:40:24 Z karma Flood (IOI07_flood) C++14
100 / 100
 567 ms 30672 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;
        u = e[i].y, v = e[j].y;
        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 = (a - b) * (b - c); // t > 0 -> lef, t < 0 -> rig
    //cout << t << ' ';
    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(a.x <= b.x || a.y <= b.y) {
       if(t > 0) return 2; // uu tien sang phai
       else return 0;
    } 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:58:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
flood.cpp: In function 'int main()':
flood.cpp:64: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:65: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
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

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

Subtask #5
10.0 / 10.0

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

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 7 ms 5112 KB Output is correct

Subtask #8
3.0 / 3.0

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

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5084 KB Output is correct
2 Correct 7 ms 5240 KB Output is correct

Subtask #10
9.0 / 9.0

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

Subtask #11
9.0 / 9.0

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

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 19376 KB Output is correct
2 Correct 565 ms 26980 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 24344 KB Output is correct
2 Correct 567 ms 30672 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 26796 KB Output is correct
2 Correct 314 ms 25828 KB Output is correct