oj.uz

Submission #344365

# Submission time Handle Problem Language Result Execution time Memory
344365 2021-01-05T14:34:20 Z Joshc Flood (IOI07_flood) C++11
100 / 100
 355 ms 21860 KB 
#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;

const int MAX_N = 100001;

int x[MAX_N], y[MAX_N], p[2*MAX_N], q[2*MAX_N], m[2*MAX_N], m2[2*MAX_N], left[2*MAX_N], num[2*MAX_N];
bool done[2*MAX_N];
vector<pair<int, int> > edges[MAX_N];

int dir(int a, int b) {
    if (x[a] == x[b]) return y[a]<y[b] ? 0 : 2;
    return x[a]<x[b] ? 3 : 1;
}

bool comp(int a, int b) {
    if ((dir(p[a], q[a])&1) != (dir(p[b], q[b])&1)) return dir(p[b], q[b])&1;
    if (dir(p[a], q[a])&1) return y[p[a]] > y[p[b]];
    return x[p[a]] < x[p[b]];
}

int main() {
    int n, w, ans=0;
    scanf("%d", &n);
    for (int i=1; i<=n; i++) scanf("%d%d", &x[i], &y[i]);
    scanf("%d", &w);
    for (int i=1; i<=w; i++) {
        scanf("%d%d", &p[i], &q[i]);
        edges[p[i]].push_back({q[i], i});
        edges[q[i]].push_back({p[i], i});
        left[i] = min(x[p[i]], x[q[i]]);
        done[i] = false;
    }
    vector<int> v;
    set<int> s;
    for (int i=1; i<=w; i++) {
        v.push_back(i);
        s.insert(i);
    }
    sort(v.begin(), v.end(), comp);
    for (int i=0; i<w; i++) {
        m[i+1] = v[i];
        m2[v[i]] = i+1;
    }
    while (!s.empty()) {
        int a = m[*s.begin()];
        int start = p[a], cur=q[a];
        if (dir(start, cur)<2) swap(start, cur);
        int d = dir(start, cur), orig=cur;
        set<int> del = {a};
        num[a]++;
        while (true) {
            if (!cur) break;
            int angle=4;
            pair<int, int> best;
            for (auto v : edges[cur]) {
                if (done[v.second]) continue;
                int x = (dir(cur, v.first)-d+5)%4;
                if (x < angle) {
                    angle = x;
                    best = v;
                }
            }
            if (cur==start && orig==best.first) break;
            num[best.second]++;
            del.insert(best.second);
            d = dir(cur, best.first);
            cur = best.first;
        }
        for (int i : del) {
            s.erase(m2[i]);
            done[i] = true;
        }
    }
    for (int i=1; i<=w; i++) ans += num[i]==2;
    printf("%d\n", ans);
    for (int i=1; i<=w; i++) {
        if (num[i] == 2) printf("%d\n", i);
    }
}

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
flood.cpp:27:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |     for (int i=1; i<=n; i++) scanf("%d%d", &x[i], &y[i]);
      |                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~
flood.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |     scanf("%d", &w);
      |     ~~~~~^~~~~~~~~~
flood.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |         scanf("%d%d", &p[i], &q[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

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

Subtask #9
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5228 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 12644 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 13048 KB Output is correct
2 Correct 355 ms 19680 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 17396 KB Output is correct
2 Correct 297 ms 20448 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 19424 KB Output is correct
2 Correct 278 ms 21860 KB Output is correct