QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#409570 | #7511. Planar Graph | grass8cow# | WA | 1ms | 4192kb | C++17 | 2.1kb | 2024-05-12 11:31:16 | 2024-05-12 11:31:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m,e,U[1010],d[1010],V[1010];
ll X[1010],Y[1010];
struct no{
ll x,y;
inline int hf(){return x>0||x==0&&y>0;}
}a[1010];
no operator - (const no &a,const no &b){return (no){a.x-b.x,a.y-b.y};}
ll cro(no a,no b){return a.x*b.y-a.y*b.x;}
bool cd(no a,no b){if(a.hf()!=b.hf())return a.hf()<b.hf();return cro(a,b)>0;}
bool vis[1010];
#define pb push_back
vector<int>g[1010];
int id[1010][1010],nx[1010];
bool vis2[1010];int be[1010];
vector<int>G[1010];int C;
bool is[1010];
int main(){
scanf("%d%d%d",&n,&m,&e);
for(int i=1;i<=n+m;i++)scanf("%lld%lld",&X[i],&Y[i]),a[i]=(no){X[i],Y[i]};
for(int i=1;i<=e;i++)scanf("%d%d",&U[i],&V[i]),d[U[i]]++,d[V[i]]++,id[U[i]][V[i]]=i*2-1,id[V[i]][U[i]]=i*2;
while(1){
bool fp=0;
for(int i=1;i<=e;i++)if(!vis[i]){
if(d[U[i]]==1||d[V[i]]==1){fp=1,vis[i]=1,d[U[i]]--,d[V[i]]--;break;}
}
if(!fp)break;
}
for(int i=1;i<=e;i++)if(!vis[i])g[U[i]].pb(V[i]),g[V[i]].pb(U[i]);
for(int i=1;i<=e;i++)if(!g[i].empty()){
sort(g[i].begin(),g[i].end(),[&](int x,int y){return cd(a[x]-a[i],a[y]-a[i]);});
int sz=g[i].size();
for(int j=0;j<sz;j++){
int x=g[i][j],y=g[i][(j+1)%sz];
if(cro(a[x]-a[i],a[y]-a[i])>0)nx[id[x][i]]=id[i][y];
else nx[id[x][i]]=-1;
}
}
for(int i=1;i<=e*2;i++)if(!vis[(i+1)/2]&&!vis2[i]){
int u=i;
if(nx[u]==-1){vis2[i]=1;continue;}
C++;
while(!vis2[u])vis2[u]=1,G[C].pb(u),be[u]=C,u=nx[u];
}
for(int i=n+1;i<=n+m;i++){
int tt=0;
for(int j=1;j<=C;j++){
ll s1=0,s2=0;
for(int k:G[j]){
int u=U[(k+1)>>1],v=V[(k+1)>>1];if(!(k&1))swap(u,v);
s1+=abs(cro(a[u]-a[i],a[v]-a[i]));
s2+=cro(a[u],a[v]);
}
s2=abs(s2);
if(s1==s2){is[j]=1,tt=1;break;}
}
if(!tt)is[0]=1;
}
for(int i=1;i<=e;i++)
if(is[be[i*2-1]]||is[be[i*2]])printf("1");else printf("0");
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3880kb
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: 1ms
memory: 3860kb
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: 4192kb
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:
011111111010111111100001011000001001110111110111101011011001111110011011101111110110011101001000000001010000101101100110000100110100101101111011000011000111111100000011
result:
wrong answer 1st lines differ - expected: '011111111111111111100001011000...1111111110011001111111100100011', found: '011111111010111111100001011000...1111011000011000111111100000011'