oj.uz

Submission #1032739

# Submission time Handle Problem Language Result Execution time Memory
1032739 2024-07-24T07:33:07 Z caterpillow Relay (COI16_relay) C++17
18 / 100
 2000 ms 10736 KB 
#include <bits/stdc++.h>

using namespace std;

using db = long double;
using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

template<typename... Args> // tuples
ostream& operator<<(ostream& os, tuple<Args...> t) { 
    apply([&](Args... args) { string dlm = "{"; ((os << dlm << args, dlm = ", "), ...); }, t);
    return os << "}";
}

template<typename T, typename V> // pairs
ostream& operator<<(ostream& os, pair<T, V> p) { return os << "{" << p.f << ", " << p.s << "}"; }

template<class T, class = decltype(begin(declval<T>()))> // iterables
typename enable_if<!is_same<T, string>::value, ostream&>::type operator<<(ostream& os, const T& v) {
    string dlm = "{";
    for (auto& i : v) os << dlm << i, dlm = ", ";
    return os << "}";  
}

template <typename T, typename... V>
void printer(string pfx, const char *names, T&& head, V&& ...tail) {
    int i = 0;
    while (names[i] && names[i] != ',') i++;
    constexpr bool is_str = is_same_v<decay_t<T>, const char*>;
    if (is_str) cerr << " " << head;
    else cerr << pfx, cerr.write(names, i) << " = " << head; 
    if constexpr (sizeof...(tail)) printer(is_str ? "" : ",", names + i + 1, tail...);
    else cerr << endl;
}

#ifdef LOCAL
#define dbg(...) printer(to_string(__LINE__) + ": ", #__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(x...)
#define cerr if (0) std::cerr
#endif

pl operator+(const pl& a, const pl& b) {
    return {a.f + b.f, a.s + b.s};
}

pl operator-(const pl& a, const pl& b) {
    return {a.f - b.f, a.s - b.s};
}

ll operator*(const pl& a, const pl& b) {
    return a.f * b.s - a.s * b.f; // cross product
}

ll dot(const pl& a, const pl& b) {
    return a.f * b.f + a.s * b.s;
}

bool comp(const pl& a, const pl& b) {
    return a * b < 0;
}

struct Line {
    pl s, t;
};

int poop(ll x) {
    if (x == 0) return 0;
    if (x > 0) return 1;
    return -1;
}

const pl origin = {0, 0};
bool inter(pl st, pl en, Line line) {
    en = en - st;
    pl x = line.s - st;
    pl y = line.t - st;
    if (x * y > 0) swap(x, y); // x -> y is clockwise
    
    int b1 = poop(x * en);
    int b2 = poop(y * en);
    if (b1 * b2 >= 0) return false; 
    if ((en - x) * (y - x) >= 0) return false;
    return true;
}

int n, m;
vt<pl> pts;
vt<pl> hull;
vt<Line> edges;

bool can_see(pl x, pl y) {
    for (auto& l : edges) {
        if (inter(x, y, l)) {
            return false;
        }
    }
    F0R (i, m) {
        if (inter(x, y, {hull[i], hull[(i + 2) % m]})) {
            return false;
        }
    }
    return true;
}

vt<vt<int>> adj;

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> n;
    pts.resize(n); 
    F0R (i, n) cin >> pts[i].f >> pts[i].s;
    cin >> m;
    hull.resize(m);
    F0R (i, m) cin >> hull[i].f >> hull[i].s;
    edges.resize(m);
    F0R (i, m) edges[i] = {hull[i], hull[(i + 1) % m]};
    
    adj.resize(n);
    F0R (i, n) {
        FOR (j, i + 1, n) {
            if (can_see(pts[i], pts[j])) adj[i].pb(j), adj[j].pb(i);
        }
    }
    vt<int> good(n);
    good[0] = 1;
    for (int u : adj[0]) {
        good[u] = true;
        for (int v : adj[u]) {
            good[v] = true;
        }
    }
    dbg(good);
    cout << accumulate(all(good), -1) << endl;
}

Compilation message

relay.cpp:121:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  121 | main() {
      | ^~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 596 KB Output is correct
2 Correct 45 ms 532 KB Output is correct
3 Correct 34 ms 584 KB Output is correct
4 Correct 33 ms 460 KB Output is correct
5 Correct 22 ms 592 KB Output is correct
6 Correct 24 ms 600 KB Output is correct
7 Correct 34 ms 600 KB Output is correct
8 Correct 31 ms 676 KB Output is correct
9 Correct 15 ms 600 KB Output is correct
10 Correct 14 ms 348 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 596 KB Output is correct
2 Correct 45 ms 532 KB Output is correct
3 Correct 34 ms 584 KB Output is correct
4 Correct 33 ms 460 KB Output is correct
5 Correct 22 ms 592 KB Output is correct
6 Correct 24 ms 600 KB Output is correct
7 Correct 34 ms 600 KB Output is correct
8 Correct 31 ms 676 KB Output is correct
9 Correct 15 ms 600 KB Output is correct
10 Correct 14 ms 348 KB Output is correct
11 Execution timed out 2066 ms 1620 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 596 KB Output is correct
2 Correct 45 ms 532 KB Output is correct
3 Correct 34 ms 584 KB Output is correct
4 Correct 33 ms 460 KB Output is correct
5 Correct 22 ms 592 KB Output is correct
6 Correct 24 ms 600 KB Output is correct
7 Correct 34 ms 600 KB Output is correct
8 Correct 31 ms 676 KB Output is correct
9 Correct 15 ms 600 KB Output is correct
10 Correct 14 ms 348 KB Output is correct
11 Execution timed out 2052 ms 10736 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 596 KB Output is correct
2 Correct 45 ms 532 KB Output is correct
3 Correct 34 ms 584 KB Output is correct
4 Correct 33 ms 460 KB Output is correct
5 Correct 22 ms 592 KB Output is correct
6 Correct 24 ms 600 KB Output is correct
7 Correct 34 ms 600 KB Output is correct
8 Correct 31 ms 676 KB Output is correct
9 Correct 15 ms 600 KB Output is correct
10 Correct 14 ms 348 KB Output is correct
11 Execution timed out 2066 ms 1620 KB Time limit exceeded
12 Halted 0 ms 0 KB -