QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#409570#7511. Planar Graphgrass8cow#WA 1ms4192kbC++172.1kb2024-05-12 11:31:162024-05-12 11:31:18

Judging History

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

  • [2024-05-12 11:31:18]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4192kb
  • [2024-05-12 11:31:16]
  • 提交

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'