QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#294121 | #7511. Planar Graph | OAleksa | WA | 5ms | 11116kb | C++14 | 3.8kb | 2023-12-30 08:01:35 | 2023-12-30 08:01:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
const int N = 310;
const int M = 1e5 + 69; //ko ce racunati ovo?
struct point {
int x, y;
} a[N], b[N];
int n, m, e, c[N], ans[N]; //kom nodu pripada
vector<int> g[M], f[M];
vector<int> t[M];
int edge[N][N];
int cross(point a, point b, point c) {
int r = (c.x - a.x) * (b.y - a.y) - (c.y - a.y) * (b.x - a.x);
if (r > 0)
return 1; //desno
else if (r < 0)
return -1; //levo
return 0;
}
bool inter(point a, point b, point c, point d) {
for (int i = 0;i < 2;i++) {
if (cross(a, b, c) == cross(a, b, d) || cross(a, b, c) == 0 || cross(a, b, d) == 0)
return false;
swap(a, c);
swap(b, d);
}
return true;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tt = 1;
//cin >> tt;
while (tt--) {
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;
}
vector<pair<int, int>> edges(e + 1);
for (int i = 1;i <= e;i++) {
cin >> edges[i].f >> edges[i].s;
edge[edges[i].f][edges[i].s] = i;
edge[edges[i].s][edges[i].f] = i;
if (edges[i].f > edges[i].s)
swap(edges[i].f, edges[i].s);
}
for (int i = 1;i <= n;i++) {
for (int j = i + 1;j <= n;j++) {
if (edge[i][j])
continue;
int o = 1;
for (int k = 0;k < e;k++) {
o &= (!inter(a[i], a[j], a[edges[k].f], a[edges[k].s]));
}
if (o) {
edges.push_back({i, j});
edge[i][j] = edge[j][i] = (int)edges.size(); //fake edges
}
}
}
int node = 1;
for (int i = 1;i <= n;i++) {
for (int j = i + 1;j <= n;j++) {
for (int k = j + 1;k <= n;k++) {
if (!edge[i][j] || !edge[i][k] || !edge[j][k])
continue;
int id = edge[i][j], id2 = edge[i][k], id3 = edge[j][k];
int o = 0;
for (int x = 1;x <= n;x++) {
int p = cross(a[i], a[j], a[x]);
int p1 = cross(a[k], a[i], a[x]);
int p2 = cross(a[j], a[k], a[x]);
o |= (p == p1 && p1 == p2);
}
if (o)
continue;
t[node].push_back(id);
t[node].push_back(id2);
t[node].push_back(id3);
f[id].push_back(node);
f[id2].push_back(node);
f[id3].push_back(node);
for (int x = 1;x <= m;x++) {
int p = cross(a[i], a[j], b[x]);
int p1 = cross(a[k], a[i], b[x]);
int p2 = cross(a[j], a[k], b[x]);
if (p == p1 && p1 == p2) {
c[x] = node;
}
}
++node;
}
}
}
//> e su fake edgevi
int cnt = 0;
for (int i = 1;i <= m;i++) {
if (c[i] == 0) {
c[i] = node;
cnt++;
}
}
if (cnt) {
for (int i = 1;i < node;i++) {
int o = 0;
for (auto u : t[i]) {
o |= (f[u].size() == 1);
}
if (o) {
g[node].push_back(i);
g[i].push_back(node);
}
}
}
for (int i = 1;i < node;i++) {
for (int j = i + 1;j < node;j++) {
for (auto u : t[i]) {
if (u > e) {
for (auto x : t[j]) {
if (x == u || inter(a[edges[u].f], a[edges[u].s], a[edges[x].f], a[edges[x].s])) {
g[i].push_back(j);
g[j].push_back(i);
}
}
}
}
}
}
for (int i = 1;i <= m;i++) {
vector<int> vis(node + 1);
function<void(int)> dfs = [&](int v) {
if (vis[v])
return;
vis[v] = 1;
for (auto u : g[v])
dfs(u);
};
dfs(c[i]);
for (int j = 1;j <= node;j++) {
if (vis[j]) {
for (auto u : t[j]) {
if (u <= e)
ans[u] = 1;
}
}
}
}
for (int i = 1;i <= e;i++)
cout << ans[i];
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 10792kb
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: 11116kb
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: 5ms
memory: 10732kb
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:
011111111111111111100001011000001001110111110111101011011001111110011011101111110111011101011001001101010100111111111111000100111100111101111111110011001111111100100011
result:
wrong answer 1st lines differ - expected: '011111111111111111100001011000...1111111110011001111111100100011', found: '011111111111111111100001011000...1111111110011001111111100100011'