QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#409568#7511. Planar Graphgrass8cow#WA 1ms3884kbC++172.1kb2024-05-12 11:29:142024-05-12 11:29:15

Judging History

你现在查看的是最新测评结果

  • [2024-05-12 11:29:15]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3884kb
  • [2024-05-12 11:29:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m,e,U[310],d[110],V[310];
ll X[210],Y[210];
struct no{
    ll x,y;
    inline int hf(){return x>0||x==0&&y>0;}
}a[210];
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[310];
#define pb push_back
vector<int>g[110];
int id[110][110],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],v=V[k];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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3784kb

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: 0ms
memory: 3884kb

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:

0111011111111

result:

wrong answer 1st lines differ - expected: '1111111111111', found: '0111011111111'