QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#224290 | #7511. Planar Graph | wxhtzdy | WA | 9ms | 31676kb | C++20 | 3.3kb | 2023-10-23 01:01:02 | 2023-10-23 01:01:03 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
int readint(){
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,m,e,idx[105][105][105],edg[105][105];
bool f[105][105],r[105][105],was[500005],res[500005],good[500005];
vector<int> g[500005],ch[500005];
struct pt{
ll x,y;
}a[105],b[105];
int orient(pt a,pt b,pt c){
ll val=a.x*(b.y-c.y)-b.x*(a.y-c.y)+c.x*(a.y-c.y);
return (val<0?-1:(val==0?0:1));
}
bool inter(pt a,pt b,pt c,pt d){
int xa=orient(a,b,c);
int xb=orient(a,b,d);
return (xa!=0&&xb!=0&&xa!=xb);
}
bool in_tri(pt a,pt b,pt c,pt d){
set<int> st;
st.insert(orient(a,b,d));
st.insert(orient(b,c,d));
st.insert(orient(c,a,d));
if(st.find(0)!=st.end()) st.erase(st.find(0));
return st.size()<=1;
}
void dfs(int x){
if(was[x]) return;
for(int i:ch[x]) res[i]=true;
was[x]=true;
for(int y:g[x]) if(!was[y]) dfs(y);
}
int main(){
n=readint(); m=readint(); e=readint();
for(int i=1;i<=n;i++) a[i].x=readint(),a[i].y=readint();
for(int i=1;i<=m;i++) b[i].x=readint(),b[i].y=readint();
for(int i=1;i<=e;i++){
int x=readint(),y=readint();
f[x][y]=f[y][x]=true;
r[x][y]=r[y][x]=true;
edg[x][y]=edg[y][x]=i;
}
for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(!f[i][j]){
f[i][j]=true;
for(int x=1;x<=n&&f[i][j];x++) for(int y=x+1;y<=n&&f[i][j];y++) if(i!=x&&i!=y&&j!=x&&j!=y&&f[x][y]){
if(inter(a[i],a[j],a[x],a[y])) f[i][j]=false;
}
}
int id=0;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
for(int k=j+1;k<=n;k++){
if(!f[i][j]||!f[i][k]||!f[j][k]) continue;
idx[i][j][k]=++id;
if(r[i][j]){
ch[id].pb(edg[i][j]);
}
if(r[i][k]){
ch[id].pb(edg[i][k]);
}
if(r[j][k]){
ch[id].pb(edg[j][k]);
}
}
}
}
int universe=++id;
for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(f[i][j]&&!r[i][j]){
vector<int> adj;
for(int k=1;k<=n;k++) if(i!=k&&j!=k&&f[i][k]&&f[j][k]) adj.pb(idx[i][j][k]);
if(adj.size()==1){
g[universe].pb(adj[0]);
g[adj[0]].pb(universe);
}
for(int x=0;x<adj.size();x++) for(int y=x+1;y<adj.size();y++){
g[adj[x]].pb(adj[y]); g[adj[y]].pb(adj[x]);
}
}
for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(r[i][j]){
vector<int> adj;
for(int k=1;k<=n;k++) if(i!=k&&j!=k&&f[i][k]&&f[j][k]) adj.pb(idx[i][j][k]);
if(adj.size()<=1){
ch[universe].pb(edg[i][j]);
}
}
for(int i=1;i<=m;i++){
int my=-1;
for(int x=1;x<=n;x++){
for(int y=x+1;y<=n;y++){
for(int z=y+1;z<=n;z++){
if(!idx[x][y][z]) continue;
if(in_tri(a[x],a[y],a[z],b[i])){
my=idx[x][y][z];
}
}
}
}
if(my==-1) good[universe]=true;
else good[my]=true;
}
for(int i=1;i<=id;i++) if(good[i]&&!was[i]) dfs(i);
for(int i=1;i<=e;i++) if(res[i]) printf("1"); else printf("0");
return 0;
}
/*
4 1 3
-2 0
0 2
2 0
0 1
0 3
1 2
2 3
1 3
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 30016kb
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: 3ms
memory: 28896kb
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: 9ms
memory: 31676kb
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:
001010001100000010000000001000001100001001010101000000000100010100000000000000000100000000000000000000000000000000000100010100001000100100000001101000000010010000000100
result:
wrong answer 1st lines differ - expected: '011111111111111111100001011000...1111111110011001111111100100011', found: '001010001100000010000000001000...0000001101000000010010000000100'