QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#224336#7511. Planar GraphwxhtzdyWA 11ms33820kbC++203.9kb2023-10-23 01:22:312023-10-23 01:22:31

Judging History

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

  • [2023-10-23 01:22:31]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:33820kb
  • [2023-10-23 01:22:31]
  • 提交

answer

#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;

template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,m,e,idx[105][105][105],edg[105][105];
bool f[105][105],r[105][105],was[500005],res[500005],good[500005],valid[105][105][105];
vector<int> g[500005],ch[500005];

struct pt{
	ll x,y;
}a[105],b[105];

int orient(pt a,pt b,pt c){
	ll val=a.x*(b.y-c.y)-b.x*(a.y-c.y)+c.x*(a.y-b.y);
	return (val<0?-1:(val==0?0:1));
}

bool inter(pt a,pt b,pt c,pt d){
	int xa=orient(a,b,c);
	int xb=orient(a,b,d);
	return (xa!=0&&xb!=0&&xa!=xb);
}

bool in_tri(pt a,pt b,pt c,pt d){
	set<int> st;
	st.insert(orient(a,b,d));
	st.insert(orient(b,c,d));
	st.insert(orient(c,a,d));
	if(st.find(0)!=st.end()) st.erase(st.find(0));
	return st.size()<=1;
}

void dfs(int x){
	if(was[x]) return;
	for(int i:ch[x]) res[i]=true;
	was[x]=true;
	for(int y:g[x]) if(!was[y]) dfs(y);
}

int main(){
	n=readint(); m=readint(); e=readint();
	for(int i=1;i<=n;i++) a[i].x=readint(),a[i].y=readint();
	for(int i=1;i<=m;i++) b[i].x=readint(),b[i].y=readint();
	for(int i=1;i<=e;i++){
		int x=readint(),y=readint();
		f[x][y]=f[y][x]=true;
		r[x][y]=r[y][x]=true;
		edg[x][y]=edg[y][x]=i;
	}
	for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(!f[i][j]){
		f[i][j]=true;
		for(int x=1;x<=n&&f[i][j];x++) for(int y=x+1;y<=n&&f[i][j];y++) if(i!=x&&i!=y&&j!=x&&j!=y&&f[x][y]){
			if(inter(a[i],a[j],a[x],a[y])) f[i][j]=false;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			for(int k=j+1;k<=n;k++){
				if(i==j||i==k||j==k||!f[i][j]||!f[i][k]||!f[j][k]) continue;
				valid[i][j][k]=true;
				for(int z=1;z<=n;z++) if(i!=z&&j!=z&&k!=z&&in_tri(a[i],a[j],a[k],a[z])){
					valid[i][j][k]=false;
					valid[i][k][j]=false;
					valid[j][i][k]=false;
					valid[j][k][i]=false;
					valid[k][i][j]=false;
					valid[k][j][i]=false;
				}
			}
		}
	}
	int id=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(!f[i][j]||!f[i][k]||!f[j][k]||!valid[i][j][k]) continue;
				idx[i][j][k]=++id;
				idx[i][k][j]=id;
				idx[j][i][k]=id;
				idx[j][k][i]=id;
				idx[k][i][j]=id;
				idx[k][j][i]=id;
				if(r[i][j]){
					ch[id].pb(edg[i][j]);
				}
				if(r[i][k]){
					ch[id].pb(edg[i][k]);
				}
				if(r[j][k]){
					ch[id].pb(edg[j][k]);
				}
			}
		}
	}
	int universe=++id;
	for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(f[i][j]&&!r[i][j]){
		vector<int> adj;
		for(int k=1;k<=n;k++) if(i!=k&&j!=k&&f[i][k]&&f[j][k]&&idx[i][j][k]) adj.pb(idx[i][j][k]);
		if(adj.size()==1){
			g[universe].pb(adj[0]);
			g[adj[0]].pb(universe);
		}
		for(int x=0;x<adj.size();x++) for(int y=x+1;y<adj.size();y++){
			g[adj[x]].pb(adj[y]); g[adj[y]].pb(adj[x]);
		}
	}
	for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(r[i][j]){
		vector<int> adj;
		for(int k=1;k<=n;k++) if(i!=k&&j!=k&&f[i][k]&&f[j][k]&&idx[i][j][k]) adj.pb(idx[i][j][k]);
		if(adj.size()<=1){
			ch[universe].pb(edg[i][j]);
		}
	}
	for(int i=1;i<=m;i++){
		int my=-1;
		for(int x=1;x<=n;x++){
			for(int y=x+1;y<=n;y++){
				for(int z=y+1;z<=n;z++){
					if(!idx[x][y][z]) continue;
					if(in_tri(a[x],a[y],a[z],b[i])&&valid[x][y][z]){
						my=idx[x][y][z];
					}
				}
			}
		}
		if(my==-1) good[universe]=true;
		else good[my]=true;
	}
	for(int i=1;i<=id;i++) if(good[i]&&!was[i]) dfs(i);
	for(int i=1;i<=e;i++) if(res[i]) printf("1"); else printf("0");
	return 0;
}

/*
4 1 3
-2 0
0 2
2 0
0 1
0 3
1 2
2 3
1 3
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 29796kb

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: 4ms
memory: 31972kb

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: 11ms
memory: 33820kb

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:

011111111111111111101001011000001011110111110111101111111001111111111011101111111111011101011001001001111100111111111110000101110100101101111111110011001111111100110011

result:

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