QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#293880 | #7511. Planar Graph | AlphaMale06 | RE | 1ms | 3916kb | C++14 | 5.6kb | 2023-12-29 21:44:32 | 2023-12-29 21:44:32 |
Judging History
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