QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#293880#7511. Planar GraphAlphaMale06RE 1ms3916kbC++145.6kb2023-12-29 21:44:322023-12-29 21:44:32

Judging History

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

  • [2023-12-29 21:44:32]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3916kb
  • [2023-12-29 21:44:32]
  • 提交

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;
	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 & A, point & B, point & C, 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){
	return (isLeft(a.a, a.b, b.a) != isLeft(a.a, a.b, b.b) && isLeft(b.a, b.b, a.a) != isLeft(b.a, b.b, a.b));
}

bool sharePoint(edge & a, edge & b){
	return (a.a.index==b.a.index||a.a.index==b.b.index||a.b.index==b.a.index||a.b.index==b.b.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;
		a.index=i;
		tpoint.pb(a);
	}
}

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

void InputEdges(int n){
	for(int i=0; i< n; i++){
		int x, y;
		cin >> x >> y;
		x--; y--;
		edge a;
		a.a=tpoint[x];
		a.b=tpoint[y];
		indedge[x][y]=indedge[y][x]=a.index=edges.size();
		edges.pb(a);
		exs[x][y]=exs[y][x]=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;
	}
	//podelis na trouglove (dodas fake edgeve)
	for(int i=0; i< n; i++){
		for(int j=i+1; j< n; j++){
			if(!exs[i][j]){ //nisi do sad dodao taj edge
				bool ok=1;
				edge ne; ne.a=tpoint[i]; ne.b=tpoint[j]; ne.index=edges.size();
				for(edge ed : edges){
					if(sharePoint(ed, ne))continue; //ako dele zajednicku tacku to se ne racuna kao da se seku
					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; //za svaki edge samo pamtis koje trouglove sadrzi
	}
	//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]){
					bool ok=1;
					point p1, p2, p3;
					p1=tpoint[i]; p2=tpoint[j]; p3=tpoint[k];
					for(int l=0; l<n; l++){
						if(l!=i && l!=j && l!=k){
							if(isin(p1, p2, p3, tpoint[l])){
								ok=0;
								break;
							}
						}
					}
					if(ok){
						triangle nt;			
						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;
						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++){ //za svaku fake granu dodas edge 
		if(te[i].S==-1){ //ako je na obodu dodas izmedju spolja i trougla u kom se nalazi
			adj[0].pb(te[i].F);
			adj[te[i].F].pb(0);
		}
		else{ //ako je izmedju 2 trougla dodas izmedju 2 trougla u kojima se nalazi
			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(isin(tr.A, tr.B, tr.C, 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: 3556kb

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

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: 0
Accepted
time: 1ms
memory: 3864kb

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:

011111111111111111100001011000001001110111110111101011011001111110011011101111110111011101001000000001010100111111100110000100110100101101111111110011001111111100100011

result:

ok single line: '011111111111111111100001011000...1111111110011001111111100100011'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3804kb

input:

59 1 158
-51 8
50 48
-56 -67
19 7
33 -47
32 44
42 47
-36 -57
15 34
-8 23
-24 43
20 11
61 -41
58 -11
-68 -45
36 -54
-21 42
-28 -49
-28 -31
-34 20
29 -65
-13 38
-22 -36
-30 11
-40 57
64 -69
65 51
47 34
-41 31
-1 35
28 -11
58 58
13 12
-52 43
40 6
46 48
46 -59
-52 30
69 -23
-34 38
-1 -5
-12 -27
-11 24
-...

output:

00000000000000000000000000000000000000000000000000000000000001000000000000000000000000000001000000000000000000000000000000000000000000000000001000000000000000

result:

ok single line: '000000000000000000000000000000...0000000000000001000000000000000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

92 1 125
55 10
67 -85
-26 80
36 -32
44 -64
41 -50
-93 -80
-66 -92
-68 27
-79 9
87 -61
-40 -64
89 100
75 -42
59 40
60 -30
-66 27
63 90
-19 100
24 -20
-13 83
-100 -92
-83 58
-33 -70
74 -20
-55 73
-41 28
27 -31
-37 -22
40 18
-3 -2
70 79
71 29
32 -73
39 -1
17 -95
-61 56
94 -10
-79 -66
-84 87
-16 71
52 4...

output:

10010010000101001010010100101100100000001010001000000001101111101000011111000000001011000100000010100000000100011011000000110

result:

ok single line: '100100100001010010100101001011...0010100000000100011011000000110'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3916kb

input:

85 47 204
48 93
-32 10
71 70
-37 10
20 -12
-32 -56
1 -22
-46 -64
56 82
-19 63
-5 83
16 89
79 81
51 -22
43 59
33 -87
28 67
-18 38
-16 -23
18 -78
87 66
-83 29
36 58
6 -2
68 80
18 -34
-17 59
-31 -12
-37 -75
33 -79
-51 -24
-88 6
-19 62
71 -78
-51 72
-49 -45
21 41
-58 33
46 67
-11 -31
62 46
54 55
37 -14
...

output:

000110010001001101100010110101100100011110011110110101010100110011111010101110101001001011100000110101000100010011100100100110100001011010001010001010000100011000001101010110011001101111010000011001000011

result:

ok single line: '000110010001001101100010110101...0011001101111010000011001000011'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3864kb

input:

59 96 152
-75886847 147807525
335545968 317138952
262969730 -308175740
91308409 -162085508
-397786268 -191693417
-227565597 195627938
45666011 253210394
-311142459 58197832
-412164189 -270215767
-12639523 -314154358
-269901472 -366179516
-306681757 -167771007
194329800 -339296479
-12501616 -15788817...

output:

01110111111111111110101110111011101111110011100110100111110110001110111101100111100111010111111110110101110111110011111001110001111100010111110111111111

result:

ok single line: '011101111111111111101011101110...1110001111100010111110111111111'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3792kb

input:

62 1 99
-72 -45
-58 -44
-39 5
-45 -56
11 -26
-7 56
-29 -56
-70 -26
64 -64
-12 6
4 44
-14 68
-28 29
-68 -52
-21 -10
19 -37
17 -30
26 64
-40 2
-11 -30
64 -45
38 -67
43 -35
67 -49
50 72
-60 -2
-28 37
55 55
-7 42
-63 -32
71 35
-55 26
-67 -49
-42 -43
69 59
-29 5
0 -36
-1 8
-53 66
1 -6
-2 32
-51 -61
-27 6...

output:

000010000000000110001101000110000000010010000001001001100000010010000010001100010011010101001000010

result:

ok single line: '000010000000000110001101000110...0010001100010011010101001000010'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3856kb

input:

63 1 175
50549954 -224104196
-187903718 57327090
-61398050 89271831
72686467 -167765054
4226095 73332567
-80682032 -158732552
-366425325 -180661648
-210787891 -107411752
44235201 233049038
-29484914 -280845598
228925315 -106736012
-169221325 64453690
-127160591 78410226
374001485 -312357450
31528300...

output:

0000000100000000000000000000000000010000000000000000000001000000000000000010000000000000000000000000000000000010000000000000010000000000000001000000000100000101000000000001000

result:

ok single line: '000000010000000000000000000000...0000000100000101000000000001000'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

82 4 66
182782804 77923360
117828203 139218692
-110620000 89777361
273011388 138341008
294610527 -194481138
294204618 -290402347
194417551 48839146
-161919200 -261350494
-260772975 -239789170
117370125 245536520
-201599590 -82451402
291486591 84106590
296266013 309943147
-220542664 54399074
24021444...

output:

111101011111111111111111010111111101010111100110100011111111011111

result:

ok single line: '111101011111111111111111010111...1010111100110100011111111011111'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3864kb

input:

65 50 147
-581452360 190355182
-642896619 -572084384
-305018177 -539060586
-328404608 -74526018
198824769 -402666976
-604806291 420433161
646918331 -591294299
360443372 -456307852
253325248 -341024549
-656241212 302363402
524405246 -499973260
-531933602 617077471
-185233072 -318131117
-362315669 -49...

output:

011111111110100110100010010101111011110111010001101101001001111101111111011011011001001001101100100111110111001101101010100100110111100110101010100

result:

ok single line: '011111111110100110100010010101...1010100100110111100110101010100'

Test #12:

score: 0
Accepted
time: 1ms
memory: 3696kb

input:

71 1 142
26 16
-81 21
53 -64
-46 67
-37 73
46 79
66 -27
46 53
38 -44
16 44
-44 -43
-8 -30
65 12
60 2
-26 -24
7 71
-31 -27
-13 0
-80 80
77 -65
71 2
8 -53
-64 -71
52 -58
30 53
61 -18
56 -34
-80 -13
80 56
-28 -79
-43 -52
-38 77
11 -1
-30 -73
-39 30
-61 69
-41 66
16 -45
40 -51
37 40
-26 34
57 29
-15 -8
...

output:

1000000100000100000000001001000000000010101000000100000011001000000000000001000000000000000000000000000000000000000010011000000000000000000010

result:

ok single line: '100000010000010000000000100100...0000010011000000000000000000010'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

88 68 244
452074073 749836590
-422267242 -370342423
-649645359 303851355
285738514 -585228292
674035872 344344527
-564943027 45741258
301794983 564572022
349063999 218051130
668851769 598897930
596201080 -750109936
95583385 363387733
130300372 -350613210
-126422550 -684185703
-117024972 -406661982
-...

output:

1111011101010010110011001011101101100000000010100110001111000010001011100110001100101100000010001011101100010000010110111000010101010100101011011101011010011110000111010000011110110111101110011111001111101000110001000110101101001101111100111101

result:

ok single line: '111101110101001011001100101110...1000110101101001101111100111101'

Test #14:

score: 0
Accepted
time: 1ms
memory: 3604kb

input:

24 47 58
-536382548 -36211682
-617682678 630246425
-680303961 -753887401
-576626558 -547501154
-166237320 -247093489
-780629487 -564369462
745821462 -462233962
-29960131 -120134355
-215230222 568441689
-505349805 471834374
-268168811 -773902784
-436226654 -153342090
-686102938 -414449668
-318346027 ...

output:

1011111110101111101111111011101111100110100110101011111011

result:

ok single line: '1011111110101111101111111011101111100110100110101011111011'

Test #15:

score: 0
Accepted
time: 1ms
memory: 3916kb

input:

76 82 181
-835091273 636197461
-809826661 -915012307
-514114180 762992620
-801978217 -646901746
-937647819 -73101245
632623370 -798225996
-949969476 -45929520
677089833 -491546441
-818746494 -457407341
-23609804 -63980274
927682282 -371416961
-936340868 -741789992
-82906350 -740214368
-884276937 -32...

output:

1011111111110100011011111001011110100011001111111001011100111111111110011100101011101011101011111011001100001001110001101110010010101111000101010100111100011011110001100110110110011

result:

ok single line: '101111111111010001101111100101...1100011011110001100110110110011'

Test #16:

score: 0
Accepted
time: 1ms
memory: 3884kb

input:

95 1 39
1 -2
5 -59
6 23
77 57
87 -81
96 -9
20 45
-41 5
-80 -76
62 -83
-26 93
89 -61
-104 -65
55 4
50 55
61 -39
-26 -18
-90 -98
-14 38
56 -61
-100 105
92 -4
30 -98
-13 -27
-21 27
-49 95
62 20
91 24
-75 -30
68 -4
-86 84
-17 -13
-93 13
-38 -64
40 -82
63 47
-9 28
-95 7
91 -51
-50 -66
54 27
-3 -12
-8 -89...

output:

110111101111111110111011111111111111111

result:

ok single line: '110111101111111110111011111111111111111'

Test #17:

score: 0
Accepted
time: 1ms
memory: 3788kb

input:

53 1 95
249310291 444009281
-51319591 -127058272
-521364452 184610945
-21697253 -380031119
-765296404 788815734
480089046 -792178676
285516793 131912022
715950950 -65482217
36211136 -559456984
-46323546 622669323
812068024 -71601366
-6695845 -158750172
23940379 638024824
-792521738 -179875992
-72088...

output:

00000000000010000100000000000100000000000000000000000000000000000000000100000000000000000000000

result:

ok single line: '000000000000100001000000000001...0000000100000000000000000000000'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

90 87 67
-37 -98
66 -40
17 24
-32 51
-68 56
-47 78
-83 66
-16 -22
41 -12
-31 86
-1 11
42 65
-27 2
-19 -21
-54 78
-14 -77
-74 5
-46 82
-19 63
76 43
-39 -7
62 -49
68 4
-26 72
-91 0
-40 -74
9 -68
92 64
21 88
53 -55
32 -12
100 -26
9 -24
43 -93
-99 19
-76 -3
21 97
-57 -92
-28 26
-10 -95
96 -11
43 -82
22 ...

output:

1111111111111111111111111111110111111111111111111111111111111111111

result:

ok single line: '111111111111111111111111111111...1111111111111111111111111111111'

Test #19:

score: 0
Accepted
time: 1ms
memory: 3732kb

input:

27 42 12
-196639452 -910071469
556979079 -24132720
-907504137 -798429714
217201737 894945050
592735402 -891961813
351726786 -961077191
428253659 -337157490
-814353097 482187973
-746163779 14512669
-639377173 -925754520
-499592664 319782459
-500528351 591167527
-701230268 -495398846
-836405665 445706...

output:

111111111111

result:

ok single line: '111111111111'

Test #20:

score: 0
Accepted
time: 1ms
memory: 3720kb

input:

63 28 102
-65 69
73 -1
0 -30
-69 -66
48 39
3 -37
52 26
13 18
19 -61
-9 54
24 30
-62 58
-64 -64
-6 -3
48 -24
-58 -59
-45 -1
19 -44
64 13
69 -31
38 13
73 -50
-7 -43
4 58
38 56
-21 36
-36 40
-73 17
23 63
-18 63
41 14
47 68
-16 -47
-30 61
-33 43
-45 25
-31 22
-42 2
1 -40
-17 -2
-65 6
21 -58
31 -15
3 -50...

output:

011111100111111110111110011111010010001111111101100111011111111011110101110101011001111111011111111010

result:

ok single line: '011111100111111110111110011111...1110101011001111111011111111010'

Test #21:

score: 0
Accepted
time: 1ms
memory: 3864kb

input:

81 70 214
501181684 467604004
467393962 79858372
-24971604 -76855555
310835183 -451578432
529058882 -371153027
10117013 439009502
-102203223 498873755
104983339 -167287519
-234656041 548196249
-355162848 -403411047
-303715296 -31203991
412378489 -143945211
-38540379 -474967805
-321224760 115499601
-...

output:

0010100000110011101001110011111111000011110110011000110000111111000110011111000001000100111000101111110111101011101110100000001101010100110100011011111111000100110110010100010001101111000101110110010110011010110000

result:

ok single line: '001010000011001110100111001111...1000101110110010110011010110000'

Test #22:

score: -100
Runtime Error

input:

2 1 0
-381381789 -155480688
476986136 269997025
374524257 360034879

output:


result: