oj.uz

Submission #598926

# Submission time Handle Problem Language Result Execution time Memory
598926 2022-07-19T07:55:30 Z 이동현(#8460) The Forest of Fangorn (CEOI14_fangorn) C++17
10 / 100
 3000 ms 340 KB 
#include <bits/stdc++.h>

using namespace std;

int h, w, sx, sy;
int n, m;

int pr[(int)1e5 + 4];

int fd(int x){
    return (x == pr[x] ? x : pr[x] = fd(pr[x]));
}

void unite(int x, int y){
    x = fd(x), y = fd(y);
    pr[x] = y;
}

inline int ccw(pair<int, int>&x, pair<int, int>&y, pair<int, int>&z){
    long long rv = (long long)(y.first - x.first) * (z.second - x.second) - (long long)(y.second - x.second) * (z.first - x.first);
    return (rv > 0 ? 1 : -1);
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> h >> w >> sx >> sy;
    cin >> m;
    vector<pair<int, int>> p;
    p.push_back({sx, sy});
    for(int i = 0; i < m; ++i){
        int x, y; cin >> x >> y;
        p.push_back({x, y});
    }
    cin >> n;
    for(int i = 0; i < n; ++i){
        int x, y; cin >> x >> y;
        p.push_back({x, y});
    }
    for(int i = 0; i < (int)p.size(); ++i){
        pr[i] = i;
    }
    for(int i = 0; i < (int)p.size(); ++i){
        for(int j = i + 1; j < (int)p.size(); ++j){
            if(fd(i) == fd(j)) continue;
            int can = 1;
            for(int x = m + 1; x < (int)p.size(); ++x){
                for(int y = x + 1; y < (int)p.size(); ++y){
                    if(ccw(p[i], p[j], p[x]) == ccw(p[i], p[j], p[y]) && ccw(p[x], p[y], p[i]) != ccw(p[x], p[y], p[j])){
                        can = 0;
                        break;
                    }
                }
                if(!can) break;
            }
            if(can){
                unite(i, j);
            }
        }
    }
    vector<int> ans;
    for(int i = 1; i <= m; ++i){
        if(fd(0) == fd(i)){
            ans.push_back(i);
        }
    }
    cout << (int)ans.size() << '\n';
    for(auto&i:ans) cout << i << ' ';
    return 0;
}

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Incorrect 1 ms 324 KB Output isn't correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 2 ms 212 KB Output isn't correct

Subtask #2
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 4 ms 212 KB Output is correct
4 Correct 5 ms 212 KB Output is correct
5 Correct 4 ms 212 KB Output is correct
6 Correct 19 ms 212 KB Output is correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 4 ms 212 KB Output is correct
10 Correct 62 ms 312 KB Output is correct
11 Correct 77 ms 308 KB Output is correct
12 Correct 79 ms 332 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3047 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -