Submission #158245

#	Time	Username	Problem	Language	Result	Execution time	Memory
158245		karma	Flood (IOI07_flood)	C++14	48 / 100	522 ms	26840 KiB

flood

#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 (stderr)

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 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 3 / 3
• Subtask 5: 10 / 10
• Subtask 6: 3 / 3
• Subtask 7: 3 / 3
• Subtask 8: 0 / 3
• Subtask 9: 0 / 3
• Subtask 10: 0 / 9
• Subtask 11: 9 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9