QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#189331 | #7511. Planar Graph | ucup-team1209# | WA | 2ms | 15824kb | C++20 | 3.7kb | 2023-09-27 12:10:40 | 2023-09-27 12:10:42 |
Judging History
answer
#include<bits/stdc++.h>
using ll = long long;
using std::cin;
using std::cout;
const int N = 200005;
struct vec2 { ll x, y; } a[N], b[N];
ll operator * (vec2 x, vec2 y) { return x.x * y.y - x.y * y.x; }
vec2 operator + (vec2 x, vec2 y) { return {x.x + y.x, x.y + y.y}; }
vec2 operator - (vec2 x, vec2 y) { return {x.x - y.x, x.y - y.y}; }
int half(vec2 x) { return x.y < 0 || (x.y == 0 && x.x <= 0); }
int cmp(vec2 a, vec2 b) { return half(a) == half(b) ? a * b > 0 : half(b); }
int n, m, e;
using pr = std::pair<int, int>;
std::vector<pr> edge[N];
int anc[N];
int ok[N];
vec2 start[N];
int find(int x) {
return anc[x] == x ? x : anc[x] = find(anc[x]);
}
int go[N];
void un(int x, int y) {
go[x] = y;
anc[find(x)] = find(y);
}
std::vector<pr> v;
int vis[N];
int contain(std::vector<vec2> a, vec2 o) {
bool in = 0;
for(int i = 0;i < (int) a.size();++i) {
vec2 x = a[i] - o, y = a[(i + 1) % a.size()] - o;
if(x.y > y.y) std::swap(x, y);
if(x.y <= 0 && y.y > 0 && x * y < 0) in ^= 1;
}
return in;
}
int main() {
std::ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> m >> e;
for(int i = 1;i <= n;++i) {
cin >> a[i].x >> a[i].y;
}
for(int i = 1;i <= m;++i) {
cin >> b[i].x >> b[i].y;
}
for(int i = 1;i <= e * 2 + 1;++i) anc[i] = i;
for(int i = 1, x, y;i <= e;++i) {
cin >> x >> y;
edge[x].emplace_back(y, i * 2 + 0);
edge[y].emplace_back(x, i * 2 + 1);
start[i * 2] = a[x];
start[i * 2 + 1] = a[y];
v.emplace_back(x, y);
}
for(int i = 1;i <= n;++i) {
sort(edge[i].begin(), edge[i].end(), [&](pr x, pr y) {
vec2 u = a[x.first] - a[i];
vec2 v = a[y.first] - a[i];
return cmp(u, v);
});
auto edge = ::edge[i];
for(int i = 0;i < (int) edge.size();++i) {
un(edge[i].second, edge[(i + 1) % edge.size()].second ^ 1);
}
}
std::vector<int> out;
std::vector<std::pair<std::vector<vec2>, int>> A, B;
for(int i = 2;i <= e * 2 + 1;++i) if(!vis[i]) {
int j = go[i];
vis[i] = 1;
std::vector<vec2> ss = {start[i]};
for(;j != i;j = go[j]) {
vis[j] = 1;
ss.push_back({start[j]});
}
ll sum = 0;
for(int i = 2;i < (int) ss.size();++i) {
sum += (ss[i - 1] - ss[0]) * (ss[i] - ss[0]);
}
if(sum >= 0) {
B.emplace_back(ss, i);
} else {
A.emplace_back(ss, i);
}
}
for(auto [b, bid] : B) {
int id = -1; ll S = 9e18;
for(auto [ss, ID] : A) {
ll sum = 0;
for(int i = 2;i < (int) ss.size();++i) {
sum += (ss[i - 1] - ss[0]) * (ss[i] - ss[0]);
}
sum *= -1;
if(sum >= S) {
continue;
}
int ok = 1;
for(auto x : b) {
ok = ok && contain(ss, x);
}
if(ok) {
S = sum;
id = ID;
}
}
if(id > 0) {
un(bid, id);
} else {
out.push_back(bid);
}
}
for(int i = 1;i < (int) out.size();++i) {
un(out[i - 1], out[i]);
}
for(int i = 1;i <= m;++i) {
int id = -1;
ll A = 1e18, B = 1;
for(int j = 0;j < e;++j) {
auto [x, y] = v[j];
auto u = a[x];
auto v = a[y];
if(u.y > b[i].y && v.y > b[i].y) {
continue;
}
if(u.y < b[i].y && v.y < b[i].y) {
continue;
}
ll C = (u.y - b[i].y) * v.x + (b[i].y - v.y) * u.x;
ll D = (u.y - v.y);
if(!D) continue;
if(D < 0) C *= -1, D *= -1;
using i128 = __int128;
if((i128) C < (i128) b[i].x * D) {
continue;
}
if((i128) A * D > (i128) C * B) {
A = C;
B = D;
id = j * 2 + 2;
if(u.y > v.y) {
id += 1;
}
}
}
if(id > 0) ok[find(id)] = 1;
else {
for(int x : out) ok[find(x)] = 1;
}
}
for(int i = 1;i <= e;++i) {
if(ok[find(i * 2)] || ok[find(i * 2 + 1)]) {
cout.put(1 + 48);
} else {
cout.put(0 + 48);
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 15772kb
input:
4 1 3 -2 0 0 2 2 0 0 1 0 3 1 2 2 3 1 3
output:
111
result:
ok single line: '111'
Test #2:
score: 0
Accepted
time: 0ms
memory: 15756kb
input:
13 35 13 13 12 16 -3 18 4 4 -7 23 -22 9 -23 23 11 12 -1 19 -5 15 -15 5 -15 -17 11 -17 -13 -20 19 11 -12 -10 14 -3 14 7 -4 -10 -23 -19 -12 -13 1 -22 10 -21 -1 18 -9 -8 1 13 22 12 -23 -9 -9 -12 -20 4 -3 -6 17 14 -10 10 13 -5 -2 -4 -12 13 22 -18 -21 19 5 12 -18 4 0 3 -17 5 -2 -2 0 8 0 -8 1 14 -18 3 -9 ...
output:
1111111111111
result:
ok single line: '1111111111111'
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 15824kb
input:
68 59 168 51 -57 -26 -51 -31 58 -45 -78 -46 -49 -53 14 76 -69 -64 32 58 -49 -1 12 -65 28 -15 -10 29 -53 25 -32 78 -41 24 -37 69 56 54 -10 3 36 -18 46 53 -30 41 -2 -30 13 -58 -37 -20 42 -48 -38 -42 22 64 0 9 -56 7 -11 -66 -23 19 -9 -26 -6 -61 -68 57 13 -13 50 -15 -11 -77 47 -77 57 78 51 -37 56 -75 24...
output:
011111111111111111100001011000001001110111110111101011011001111110011011101111110111011101100000000001010100110111100110000100110100101101111111110011001111111100100011
result:
wrong answer 1st lines differ - expected: '011111111111111111100001011000...1111111110011001111111100100011', found: '011111111111111111100001011000...1111111110011001111111100100011'