oj.uz

답안 #598926

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3047 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -