QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#294184#7511. Planar GraphOAleksaWA 2ms4412kbC++143.6kb2023-12-30 09:30:232023-12-30 09:30:24

Judging History

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

  • [2023-12-30 09:30:24]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4412kb
  • [2023-12-30 09:30:23]
  • 提交

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 = 1e4 + 69; //ko ce racunati ovo?
struct point {
	int x, y;
} a[N], b[N];
int n, m, e, c[M], ans[N], z[M]; 
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);
    for (int i = 0;i < e;i++) {
    	cin >> edges[i].f >> edges[i].s;
    	edge[edges[i].f][edges[i].s] = i + 1;
    	edge[edges[i].s][edges[i].f] = i + 1;
    	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 (auto u : edges) {
    			o &= (!inter(a[i], a[j], a[u.f], a[u.s]));
    		}
    		if (o) {
    			edges.push_back({i, j});
    			edge[i][j] = edge[j][i] = (int)edges.size(); //fake edges
    		}
    	}
    }
    vector<int> v;
    int node = 1, cnt = 0;
   	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) {
							v.push_back(node);
							++cnt;
						}
   				}
   				++node;
   			}
   		}
   	}
   	//> e su fake edgevi
   	if (cnt != m)
   		v.push_back(node);
   	for (int i = e;i < (int)edges.size();i++) {
   		if (f[i].size() == 2) {
   			g[f[i].front()].push_back(f[i].back());
   			g[f[i].back()].push_back(f[i].front());
   		}
   		else {
   			g[f[i].front()].push_back(node);
   			g[node].push_back(f[i].front());
   		}
   	}
   	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);
   	};
   	for (auto u : v) {
   		if (!vis[u])
   			dfs(u);
   	}
   	if (vis[node]) {
   		for (int i = 1;i <= e;i++) {
   			if (f[i].size() == 1)
   				ans[i] = 1;
   		}
   	}
		for (int i = 1;i <= node;i++) {
			if (vis[i]) {
				for (auto u : t[i]) {
					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: 1ms
memory: 4376kb

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

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

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:

011111111111111111100001011000001001110111110111101011011001111110011011101111110111011101001000000001010100111111100110000100110100101101111111010011001111111100100011

result:

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