Submission #3416087
Source Code Expand
#include<bits/stdc++.h>
#define gc getchar()
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,v) rep(i,0,(int)v.size()-1)
#define lint long long
#define db double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define debug(x) cerr<<#x<<"="<<x
#define sp <<" "
#define ln <<endl
#define N 100010
#define on_bj(p) (p.x==0||p.x==r||p.y==0||p.y==c)
#define NO return !printf("NO\n")
using namespace std;
typedef pair<int,int> pii;
typedef set<int>::iterator sit;
inline int inn()
{
int x,ch;while((ch=gc)<'0'||ch>'9');
x=ch^'0';while((ch=gc)>='0'&&ch<='9')
x=(x<<1)+(x<<3)+(ch^'0');return x;
}
struct P{
int x,y;
inline int init() { return x=inn(),y=inn(); }
};pair<P,P> p[N];
inline int gabs(int x) { return x<0?-x:x; }
inline int rot(P &p,int r,int c)
{
if(p.y==0) return p.y=p.x,p.x=c;
if(p.x==r) return p.x=c-p.y,p.y=r;
if(p.y==c) return p.y=p.x,p.x=0;
if(p.x==0) return p.x=c-p.y,p.y=0;
return 0;
}
pii L[N];
inline int rev(P &p,int r,int c) { return p.x=r-p.x,p.y=c-p.y; }
inline int solve(int n,int r,int c)
{
int cnt=0;
rep(i,1,n) if(p[i].fir.x>p[i].sec.x) swap(p[i].fir,p[i].sec);
rep(i,1,n) if(p[i].fir.x==0&&p[i].sec.x!=0)
{
cnt++;
if(p[i].sec.y==0) L[cnt]=mp(p[i].fir.x,p[i].sec.x);
else if(p[i].sec.y<r) L[cnt]=mp(p[i].fir.x,c+p[i].sec.y);
else L[cnt]=mp(p[i].fir.x,c+r+(c-p[i].sec.x));
}
sort(L+1,L+cnt+1);
rep(i,1,cnt-1) if(L[i].sec>L[i+1].sec) return 0;
int ld=-1,lu=r+1;
rep(i,1,n) if(p[i].fir.x==0&&p[i].sec.x!=0&&p[i].sec.y==0) ld=max(ld,p[i].sec.x);
rep(i,1,n) if(p[i].sec.x==r&&p[i].fir.x!=r&&p[i].fir.y==0) lu=min(lu,p[i].fir.x);
if(ld>lu) return 0;cnt=0;
rep(i,1,n) if(p[i].fir.x==0&&p[i].sec.x==0)
{
if(p[i].fir.y>p[i].sec.y) swap(p[i].fir,p[i].sec);
L[++cnt]=mp(p[i].fir.y,1),L[++cnt]=mp(p[i].sec.y,-1);
}
rep(i,1,n)
{
if(p[i].fir.x==0&&p[i].sec.x!=0) L[++cnt]=mp(p[i].fir.y+1,-2);
if(p[i].sec.x==0&&p[i].sec.x!=0) L[++cnt]=mp(p[i].sec.y+1,-2);
if(p[i].fir.x==0&&p[i].sec.x==0) L[++cnt]=mp(p[i].fir.y+1,-2);
}
sort(L+1,L+cnt+1);int q=0;
rep(i,1,cnt)
{
if(L[i].sec==-2) { if(q) return 0; }
else q+=L[i].sec;
}
cnt=0;
rep(i,1,n) if(p[i].fir.y==0&&p[i].sec.y==0)
L[++cnt]=mp(p[i].fir.x,1),L[++cnt]=mp(p[i].sec.x,-1);
rep(i,1,n)
{
if(p[i].fir.y==0&&p[i].sec.y!=0) L[++cnt]=mp(p[i].fir.x+1,-2);
if(p[i].sec.y==0&&p[i].fir.y!=0) L[++cnt]=mp(p[i].sec.x+1,-2);
if(p[i].fir.y==0&&p[i].sec.y==0) L[++cnt]=mp(p[i].fir.x+1,-2);
}
sort(L+1,L+cnt+1);q=0;
rep(i,1,cnt)
{
if(L[i].sec==-2) { if(q) return 0; }
else q+=L[i].sec;
}
return 1;
}
int main()
{
int r=inn(),c=inn(),n=inn(),cnt=0;
rep(i,1,n)
{
static P p1,p2;p1.init(),p2.init();
if(!on_bj(p1)||!on_bj(p2)) continue;
p[++cnt]=mp(p1,p2);
}
n=cnt;int ud=0,lr=0;
rep(i,1,n) if(gabs(p[i].fir.x-p[i].sec.x)==r) ud=1;
rep(i,1,n) if(gabs(p[i].fir.y-p[i].sec.y)==c) lr=1;
if(ud&&lr) NO;
if(lr) { rep(i,1,n) rot(p[i].fir,r,c),rot(p[i].sec,r,c);swap(r,c); }
rep(i,1,n) if(p[i].fir.x>p[i].sec.x) swap(p[i].fir,p[i].sec);
if(!solve(n,r,c)) NO;
rep(i,1,n) rev(p[i].fir,r,c),rev(p[i].sec,r,c);
if(!solve(n,r,c)) NO;
return !printf("YES\n");
}
Submission Info
Submission Time |
|
Task |
E - Connected? |
User |
kevinshuai |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3236 Byte |
Status |
WA |
Exec Time |
39 ms |
Memory |
2560 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 700 |
Status |
|
|
Set Name |
Test Cases |
Sample |
s1.txt, s2.txt, s3.txt, s4.txt |
All |
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 43.txt, 44.txt, 45.txt, 46.txt, s1.txt, s2.txt, s3.txt, s4.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
WA |
33 ms |
1792 KB |
02.txt |
WA |
33 ms |
1536 KB |
03.txt |
WA |
33 ms |
1408 KB |
04.txt |
WA |
29 ms |
640 KB |
05.txt |
WA |
32 ms |
1408 KB |
06.txt |
WA |
36 ms |
2432 KB |
07.txt |
AC |
30 ms |
512 KB |
08.txt |
AC |
35 ms |
1664 KB |
09.txt |
AC |
32 ms |
1024 KB |
10.txt |
AC |
37 ms |
2304 KB |
11.txt |
AC |
36 ms |
1920 KB |
12.txt |
WA |
28 ms |
256 KB |
13.txt |
WA |
29 ms |
512 KB |
14.txt |
AC |
26 ms |
1024 KB |
15.txt |
AC |
29 ms |
1024 KB |
16.txt |
WA |
30 ms |
384 KB |
17.txt |
WA |
30 ms |
256 KB |
18.txt |
WA |
28 ms |
256 KB |
19.txt |
AC |
29 ms |
640 KB |
20.txt |
AC |
31 ms |
2048 KB |
21.txt |
AC |
30 ms |
896 KB |
22.txt |
AC |
31 ms |
1152 KB |
23.txt |
AC |
26 ms |
1792 KB |
24.txt |
AC |
30 ms |
2048 KB |
25.txt |
WA |
35 ms |
2304 KB |
26.txt |
AC |
39 ms |
2560 KB |
27.txt |
AC |
36 ms |
2432 KB |
28.txt |
AC |
34 ms |
2432 KB |
29.txt |
AC |
35 ms |
2432 KB |
30.txt |
AC |
35 ms |
2304 KB |
43.txt |
WA |
1 ms |
256 KB |
44.txt |
WA |
1 ms |
256 KB |
45.txt |
WA |
1 ms |
256 KB |
46.txt |
AC |
1 ms |
256 KB |
s1.txt |
AC |
1 ms |
256 KB |
s2.txt |
AC |
1 ms |
256 KB |
s3.txt |
WA |
1 ms |
256 KB |
s4.txt |
AC |
1 ms |
256 KB |