QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#224491 | #7511. Planar Graph | wxhtzdy | WA | 6ms | 31392kb | C++20 | 4.1kb | 2023-10-23 03:07:24 | 2023-10-23 03:07:25 |
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],valid[105][105][105];
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-b.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);
int ya=orient(c,d,a);
int yb=orient(c,d,b);
return (ya!=yb)&&(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;
}
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
for(int k=j+1;k<=n;k++){
if(i==j||i==k||j==k||!f[i][j]||!f[i][k]||!f[j][k]) continue;
valid[i][j][k]=true;
valid[i][k][j]=true;
valid[j][i][k]=true;
valid[j][k][i]=true;
valid[k][i][j]=true;
valid[k][j][i]=true;
for(int z=1;z<=n;z++) if(i!=z&&j!=z&&k!=z&&in_tri(a[i],a[j],a[k],a[z])){
valid[i][j][k]=false;
valid[i][k][j]=false;
valid[j][i][k]=false;
valid[j][k][i]=false;
valid[k][i][j]=false;
valid[k][j][i]=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]||!valid[i][j][k]) continue;
idx[i][j][k]=++id;
idx[i][k][j]=id;
idx[j][i][k]=id;
idx[j][k][i]=id;
idx[k][i][j]=id;
idx[k][j][i]=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]&&idx[i][j][k]) adj.pb(idx[i][j][k]);
if(adj.size()==1){
g[universe].pb(adj[0]);
g[adj[0]].pb(universe);
}
assert(adj.size()<=2);
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]&&idx[i][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])&&valid[x][y][z]){
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
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 31392kb
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: -100
Wrong Answer
time: 6ms
memory: 30592kb
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:
1111011111111
result:
wrong answer 1st lines differ - expected: '1111111111111', found: '1111011111111'