QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#293872 | #7511. Planar Graph | AlphaMale06 | WA | 1ms | 3920kb | C++14 | 5.7kb | 2023-12-29 21:24:33 | 2023-12-29 21:24:33 |
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;
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 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){
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.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();
a.order();
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();
ne.order();
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;
}
}
}
}
assert(edges.size()<=1000);
for(int i=0; i<edges.size(); i++){
te[i].F=te[i].S=-1; //za svaki edge samo znas 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]; a.order();
b.a=p3; b.b=p1; b.index=indedge[i][k]; b.order();
c.a=p1; c.b=p2; c.index=indedge[i][j]; c.order();
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: 0ms
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: 0ms
memory: 3744kb
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: 3920kb
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'