QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#294069#7511. Planar GraphOAleksaWA 1ms4108kbC++143.6kb2023-12-30 03:35:132023-12-30 03:35:15

Judging History

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

  • [2023-12-30 03:35:15]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4108kb
  • [2023-12-30 03:35:13]
  • 提交

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 = 1e4 + 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
pair<int, int> f1[M];
vector<int> g[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, c))
			return true;
		swap(a, c);
		swap(b, d);
	}
	return false;
}
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() + 1; //fake edges
    		}
    	}
    }
    for (int i = 0;i < edges.size();i++) 
    	f1[i] = {-1, -1};
    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];
   				if (id <= e) 
   					t[node].push_back(id);
   				if (id2 <= e)
   					t[node].push_back(id2);
   				if (id3 <= e)
   					t[node].push_back(id3);
   				if (f1[id].f == -1 && id > e) 
   					f1[id].f = node;
   				else if (f1[id].s == -1 && id > e)
   					f1[id].s = node;
   				if (f1[id2].f == -1 && id2 > e)
   					f1[id2].f = node;
   				else if (f1[id2].s == -1 && id2 > e)
   					f1[id2].s = node;
   				if (f1[id3].f == -1 && id3 > e) //fake edges
   					f1[id3].f = node;
   				else if (f1[id3].s == -1 && id3 > e)
   					f1[id3].s = node;
   				for (int x = 1;x <= m;x++) {
   					int p = cross(a[i], a[j], b[x]);
   					int p1 = cross(a[i], a[k], b[x]);
   					int p2 = cross(a[j], a[k], b[x]);
						if (p == p1 && p1 == p2) {
							c[x] = node;
						}
   				}
   				++node;
   			}
   		}
   	}
   	for (int i = 1;i <= m;i++) {
   		if (c[i] == 0) {
   			c[i] = node;
   		}
   	}
   	for (int i = 1;i < node;i++) {
   		g[i].push_back(node);
   		g[node].push_back(i);
   	}
   	for (int i = 1;i < node;i++) {
   		for (int j = i + 1;j < node;j++) {
   			if (f1[i].f == f1[j].f || f1[i].f == f1[j].s || f1[i].s == f1[j].f || f1[i].s == f1[j].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++) {
				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: 1ms
memory: 4108kb

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: -100
Wrong Answer
time: 1ms
memory: 4072kb

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:

1100100000000

result:

wrong answer 1st lines differ - expected: '1111111111111', found: '1100100000000'