QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#293483#7511. Planar GraphAlphaMale06WA 1ms3948kbC++145.4kb2023-12-29 11:15:512023-12-29 11:15:52

Judging History

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

  • [2023-12-29 11:15:52]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3948kb
  • [2023-12-29 11:15:51]
  • 提交

answer

#include <bits/stdc++.h>

/*
	Oce nas,
	koji si na nebesima,
	da se sveti ime Tvoje,
	da dodje carstvo Tvoje,
	da bude volja Tvoja,
	i na zemlji, kao i na nebu.
	
	Hleb nas nasusni daj nam danas,
	i oprosti nam dugove nase,
	kao sto i mi oprastamo duznicima svojim,
	i ne uvedi nas u iskusenje,
	no izbavi nas od zloga.
	
	Jer je Tvoje Carstvo,
	i sila, i slava,
	u vekove vekova.
	
	Amin.
*/

using namespace std;
typedef vector<int> vc;
typedef vector<vector<int>> vvc;
using ll = long long;
using ld = long double;
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define F first
#define S second
#define pb push_back
#define pf push_front
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define int long long
const int N = 101;

struct point{
	int x, y, index;
	bool equal(point p){
		return (p.x==x && p.y==y);
	}
};

struct edge{
	point a, b;
	int index;
	void order(){
		if(a.x>b.x)swap(a, b);
	}
	bool equal(edge c){
		return (a.index==c.a.index && b.index==c.b.index);
	}
};

bool isLeft(point a, point b, point c){
	return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x)>0;
}

struct triangle{
	point A, B, C;
	edge a, b, c;
	int index;
	bool isin(point p){
		bool l1, l2, l3;
		l1=isLeft(A, B, p); l2=isLeft(B, C, p); l3=isLeft(C, A, p);
		return (l1 == l2 && l2 == l3);
	}
};

bool inter(edge a, edge b){
	if(a.a.y<b.a.y)swap(a, b);
	return (isLeft(b.a, b.b, a.a) & !isLeft(b.a, b.b, a.b) & isLeft(a.a, a.b, b.b) & !isLeft(a.a, a.b, b.a));
}

bool sharePoint(edge a, edge b){
	return (a.a.index==b.a.index||a.b.index==b.b.index||a.a.index==b.b.index||a.b.index==b.a.index);
}

vector<point> spoint;
vector<point> tpoint;
vector<triangle> t;
vector<edge> edges;
pair<int, int> te[1000];
vector<int> marks;
bool exs[N][N];
vector<int> adj[1000];
vector<int> reach;
int indedge[N][N];
bool mark[1000];
bool ans[300];

void dfs(int v){
	if(v!=0)reach.pb(v);
	mark[v]=1;
	for(int to : adj[v]){
		if(!mark[to])dfs(to);
	}
}

void InputTrianglePoints(int n){
	for(int i=0; i< n; i++){
		point a;
		cin >> a.x >> a.y;
		tpoint.pb(a);
	}
	for(int i=0; i< n; i++){
		tpoint[i].index=i;
	}
}

void InputSourcePoints(int n){
	for(int i=0; i< n; i++){
		point a;
		cin >> a.x >> a.y;
		spoint.pb(a);
	}
}

void InputEdges(int n){
	for(int i=0; i< n; i++){
		int x, y;
		cin >> x >> y;
		edge a;
		a.a=tpoint[x-1];
		a.b=tpoint[y-1];
		indedge[x-1][y-1]=indedge[y-1][x-1]=a.index=edges.size();
		edges.pb(a);
		exs[x-1][y-1]=exs[y-1][x-1]=1;
	}
}

void solve(){
	int n, m, e;
	cin >> n >> m >> e;
	InputTrianglePoints(n);
	InputSourcePoints(m);
	InputEdges(e);
	if(n==2 && e>=1){
		cout << 1;
		return;
	}
	for(edge& ed : edges)ed.order();

	//podelis na trouglove (dodas fake edgeve)
	for(int i=0; i< n; i++){
		for(int j=i+1; j< n; j++){
			bool ok=1;
			edge ne; ne.a=tpoint[i]; ne.b=tpoint[j]; ne.index=edges.size();
			ne.order();
			for(edge ed : edges){
				if(ed.equal(ne)){
					ok=0; break;
				}
				if(sharePoint(ed, ne))continue;
				if(inter(ed, ne)){
					ok=0; break;
				}
			}
			if(ok){
				edges.pb(ne);
				exs[i][j]=exs[j][i]=1;
				indedge[i][j]=indedge[j][i]=ne.index;
			}
			
		}
	}
	for(int i=0; i<=edges.size(); i++){
		te[i].F=te[i].S=-1;
	}
	//napravis same trouglove
	for(int i=0; i< n; i++){
		for(int j=i+1; j< n; j++){
			for(int k=j+1; k< n; k++){
				if(exs[i][j] && exs[i][k] && exs[j][k]){
					triangle nt;
					point p1, p2, p3;
					p1=tpoint[i]; p2=tpoint[j]; p3=tpoint[k];
					nt.A=p1;
					nt.B=p2;
					nt.C=p3;
					nt.index=t.size()+1;
					edge a, b, c; 
					a.a=p2; a.b=p3; a.index=indedge[j][k];
					b.a=p3; b.b=p1; b.index=indedge[i][k];
					c.a=p1; c.b=p2; c.index=indedge[i][j];
					nt.a=a; nt.b=b; nt.c=c;
					bool ok=1;
					for(int l=0; l<n; l++){
						if(l!=i && l!=j && l!=k){
							if(nt.isin(tpoint[l])){
								ok=0;
								break;
							}
						}
					}
					if(ok){
						t.pb(nt);
						if(te[a.index].F==-1)te[a.index].F=nt.index;
						else te[a.index].S=nt.index;
						if(te[b.index].F==-1)te[b.index].F=nt.index;
						else te[b.index].S=nt.index;
						if(te[c.index].F==-1)te[c.index].F=nt.index;
						else te[c.index].S=nt.index;
					}
				}
			}
		}
	}
	//nadjes grane u grafu
	for(int i=e; i<edges.size(); i++){
		if(te[i].S==-1){
			adj[0].pb(te[i].F);
			adj[te[i].F].pb(0);
		}
		else{
			adj[te[i].F].pb(te[i].S);
			adj[te[i].S].pb(te[i].F);
		}
	}
	//nadjes za svaki trougao da li je tacka u njemu, i da li postoji spoljasnja tacka
	int cnt=0;
	for(int i=0; i< t.size(); i++){
		triangle tr = t[i];
		bool ok=0;
		for(point p : spoint){
			if(tr.isin(p)){
				cnt++;
				ok=1;
			}
		}
		if(ok){
			marks.pb(i+1);
		}
	}
	if(cnt!=m)marks.pb(0);
	//pustis dfs
	for(int strt : marks){
		if(!mark[strt]){
			dfs(strt);
		}
	}
	if(mark[0]){
		//oznacis sve prave grane koje su na ivici
		for(int i=0; i< e; i++){
			if(te[i].S==-1){
				ans[i]=1;
			}
		}	
	}
	//za svaki trougao do kog mozes da dodjes oznacis sve njegove edgeve	
	for(int tr : reach){
		triangle tri = t[tr-1];
		if(tri.a.index<e)ans[tri.a.index]=1;
		if(tri.b.index<e)ans[tri.b.index]=1;
		if(tri.c.index<e)ans[tri.c.index]=1;
	}
	for(int i=0; i< e; i++)cout << ans[i];
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3672kb

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: 1ms
memory: 3652kb

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: 1ms
memory: 3948kb

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:

011111111111110111100001011000001101110111111111101011011001111110011011101111110111011111101001000001010010111111100111010110111100101101111111110111101111111100100011

result:

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