QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#294119#7511. Planar GraphOAleksaWA 5ms10724kbC++143.8kb2023-12-30 07:59:522023-12-30 07:59:52

Judging History

你现在查看的是最新测评结果

  • [2023-12-30 07:59:52]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:10724kb
  • [2023-12-30 07:59:52]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
const int N = 110;
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]) {
						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: 10596kb

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: 10640kb

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: 10724kb

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:

01101011111111011110000101100000100111011110011110101101100111110001101110100101001101110101000000110101010011011111111112333131441911111281147811168189111111110110111172211111130116519108131871

result:

wrong answer 1st lines differ - expected: '011111111111111111100001011000...1111111110011001111111100100011', found: '011010111111110111100001011000...0111172211111130116519108131871'