oj.uz

Submission #158244

# Submission time Handle Problem Language Result Execution time Memory
158244 2019-10-15T17:16:09 Z karma Flood (IOI07_flood) C++14
48 / 100
 523 ms 29500 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;

int Check(int a, int b, int c) {
    if(p[a].x == p[b].x) {
       if(p[b].x == p[c].x) {
          if(p[b].y < p[c].y && p[a].y < p[b].y) return 1;
          else if(p[b].y > p[c].y && p[a].y > p[b].y) return 1;
          return 3;
       }
       if(p[a].y < p[b].y) {
           if(p[b].x < p[c].x) return 2;
           return 0;
       } else {
           if(p[b].x < p[c].x) return 0;
           return 2;
       }
    } else {
       if(p[b].y == p[c].y) {
          if(p[b].x < p[c].x && p[a].x < p[b].x) return 1;
          else if(p[b].x > p[c].x && p[a].x > p[b].x) return 1;
          return 3;
       }
       if(p[a].x < p[b].x) {
           if(p[b].y < p[c].y) return 0;
           return 2;
       } else {
           if(p[b].y < p[c].y) return 2;
           return 0;
       }
    }
}

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();
            //cout << es << ' ';
            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(e[es].x, e[es].y, e[id].y) < Check(e[es].x, e[es].y, 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 << '\n';
    }
    cout << ans.size() << '\n';
    for(int i: ans) cout << i << '\n';
}

Compilation message

flood.cpp: In function 'int main()':
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".inp", "r", stdin);
        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:66: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 4984 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5032 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 5088 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 5116 KB Output is correct

Subtask #8
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 #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
0 / 9.0

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

Subtask #11
9.0 / 9.0

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

Subtask #12
0 / 9.0

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

Subtask #13
0 / 9.0

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

Subtask #14
0 / 9.0

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