QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#189349 | #7511. Planar Graph | ucup-team1209# | WA | 3ms | 15860kb | C++20 | 3.4kb | 2023-09-27 13:07:22 | 2023-09-27 13:07:24 |
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.x && !x.y) return 0;
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 ^ 1, edge[(i + 1) % edge.size()].second);
}
}
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]);
}
reverse(ss.begin(), ss.end());
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);
}
}
auto area = [&](const std::vector<vec2> & ss) {
ll sum = 0;
for(int i = 2;i < (int) ss.size();++i) {
sum += (ss[i - 1] - ss[0]) * (ss[i] - ss[0]);
}
return sum < 0 ? -sum : sum;
};
sort(A.begin(), A.end(), [&](auto x, auto y) {
return area(x.first) < area(y.first);
});
for(auto [b, bid] : B) {
int id = -1;
for(auto [ss, ID] : A) {
int ok = 1;
for(auto x : b) {
ok = ok && contain(ss, x);
}
if(ok) {
id = ID;
break;
}
}
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 seted = 0;
for(int j = 0;j < e;++j) {
for(auto [ss, ID] : A) {
if(contain(ss, b[i])) {
ok[find(ID)] = 1;
seted = 1;
break;
}
}
}
if(!seted) {
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: 3ms
memory: 13804kb
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: 3ms
memory: 15848kb
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: 0ms
memory: 15860kb
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:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
result:
wrong answer 1st lines differ - expected: '011111111111111111100001011000...1111111110011001111111100100011', found: '111111111111111111111111111111...1111111111111111111111111111111'