QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#653742#7511. Planar Graphucup-team5071#WA 11ms4084kbC++205.5kb2024-10-18 20:34:262024-10-18 20:34:28

Judging History

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

  • [2024-10-18 20:34:28]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:4084kb
  • [2024-10-18 20:34:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pt=ll;
constexpr pt eps =0;
template<typename T> struct point{
    T x,y;
    bool operator==(const point &a)const{return {abs(x-a.x)<=eps&&abs(y-a.y)<=eps};}
    bool operator<(const point &a)const{if(abs(x-a.x)<=eps)return y<a.y-eps;return x<a.x-eps;}
    bool operator>(const point &a)const{return !(*this<a||*this==a);}
    point operator+(const point &a)const{return {x+a.x,y+a.y};}
    point operator-(const point &a)const{return {x-a.x,y-a.y};}
    point operator-()const{return {-x,-y};}
    point operator*(const T k)const {return {k*x,k*y};};
    T operator*(const point &a)const{return x*a.x+y*a.y;}
    T operator^(const point &a)const{return x*a.y-y*a.x;}
    int toleft(const point &a)const{const auto t=(*this)^a;return (t>eps)-(t<-eps);}
    T len2() const{return (*this)*(*this);}
};
using Point = point<ll>;
struct argcmp
{
    bool operator()(const Point &a,const Point &b)const{
        const auto quad=[](const Point &a)
        {
            if(a.y<-eps)return 1;
            if(a.y>eps)return 4;
            if(a.x<-eps)return 5;
            if(a.x>eps)return 3;
            return 2;
        };
        const int qa=quad(a),qb=quad(b);
        if(qa!=qb)return qa<qb;
        const auto t=a^b;
        return t>eps;
    }
};

template<typename T> struct line{
    point<T> p,v;
    int toleft(const point<T> &a)const{return v.toleft(a-p);}
};
using Line = line<pt>;

template<typename T> struct segment{
    point<T> a,b;
    int is_on(const point<T> &p)const{
        if(p==a||p==b)return -1;
        return (p-a).toleft(p-b)==0&& (p-a)*(p-b)<-eps;
    }
    int is_inter(const segment<T> &s)const{
        if(is_on(s.a)||is_on(s.b)||s.is_on(a)||s.is_on(b))return -1;
        const line<T> l{a,b-a},ls{s.a,s.b-s.a};
        return l.toleft(s.a)*l.toleft(s.b)==-1&&ls.toleft(a)*ls.toleft(b)==-1;
    }
};

using Segment = segment<pt>;
using pii =pair<int,int>;
int main()
{
    int n,m,e;
    cin>>n>>m>>e;
    vector<Point>a(n+m);
    for(int i=0;i<n;i++)cin>>a[i].x>>a[i].y;
    for(int i=0;i<m;i++)cin>>a[i+n].x>>a[i+n].y;
    vector<vector<int>> edge_id(n+m,vector<int>(n+m,-1));
    vector<pair<int,int>> edges(e);
    vector<vector<pair<int,int>>> ve(n+m);
    for(int i=0;i<e;i++){
        int x,y;cin>>x>>y;
        x--,y--;
        edges[i]=make_pair(x,y);
        edge_id[x][y]=i;
        edge_id[y][x]=i;
        ve[x].emplace_back(y,1);
        ve[y].emplace_back(x,1);
    }
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n+m;j++)if(edge_id[i][j]==-1){
            int flag=1;
            Segment now{a[i],a[j]};
            for(auto [x,y]:edges)if(now.is_inter(Segment{a[x],a[y]})>0)flag=0;
            if(flag){
                ve[i].emplace_back(j,0);
                ve[j].emplace_back(i,0);
            }
        }
    }
    vector<vector<vector<pii>>> ve2(n+m);
    vector<vector<int>> point_id(n+m,vector<int>(n+m,-1));
    for(int i=0;i<n+m;i++){
        sort(ve[i].begin(),ve[i].end(),[&](pii x,pii y){
            return argcmp()(a[x.first]-a[i],a[y.first]-a[i]);
        });
        // cout<<"i="<<i<<endl;
        // for(auto [x,y]:ve[i])cout<<x<<"/"<<y<<" ";;cout<<endl;
        int cnt=0;
        for(auto [to,type]:ve[i])cnt+=type;
        if(cnt<=1){ 
            ve2[i].resize(1);
            for(auto [to,type]:ve[i])point_id[i][to]=0;
        }
        else{
            int j=0;
            while(ve[i][j].second==0)j++;
            int pr=-1,cnt=0;
            for(int tt=0;tt<ve[i].size();tt++,j=(j+1)%ve[i].size()){
                if(ve[i][j].second==1){
                    pr=cnt;
                    cnt++;
                }
                point_id[i][ve[i][j].first]=pr;
                // cout<<"i="<<i<<" cnt="<<cnt<<" j="<<j<<" to="<<ve[i][j].first<<" pr="<<pr<<endl;

            }
            ve2[i].resize(cnt);
        }
        // cout<<"give point_id i="<<i<<endl;
    }
    // cout<<"siz :";for(int i=0;i<n+m;i++)cout<<ve2[i].size()<<" ";;cout<<endl;
    string ans(e,'0');
    for(int i=0;i<n+m;i++){
        for(auto [to,type]:ve[i]){
            // cout<<"i="<<i<<" to="<<to<<" type="<<type<<endl;
            if(type){
                // cout<<"id1="<<point_id[i][to]<<" id2="<<point_id[to][i]<<endl;
                ve2[i][point_id[i][to]].emplace_back(to,(point_id[to][i]-1+ve2[to].size())%ve2[to].size());
                ve2[i][(point_id[i][to]-1+ve2[i].size())%ve2[i].size()].emplace_back(to,point_id[to][i]);
            }
            else{
                // cout<<"id1="<<point_id[i][to]<<" id2="<<point_id[to][i]<<endl;
                ve2[i][point_id[i][to]].emplace_back(to,point_id[to][i]);
            }
        }
        // cout<<"ve2 i="<<i<<" ok"<<endl;
    }
    vector<vector<int>> vis(n+m,vector<int>(n+m));
    for(int i=n;i<n+m;i++){
        queue<pair<int,int>>qu;
        if(!vis[i][0])qu.push({i,0}),vis[i][0]=1;
        while(!qu.empty()){
            auto [x,id]=qu.front();qu.pop();
            // cout<<"vis x="<<x<<" id="<<id<<endl;
            assert(id<ve2[x].size());
            for(auto [y,idy]:ve2[x][id]){
                // cout<<"e_id="<<edge_id[x][y]<<" x="<<x<<" y="<<y<<endl;
                if(edge_id[x][y]!=-1)ans[edge_id[x][y]]='1';
                if(!vis[y][idy]){
                    vis[y][idy]=1;
                    qu.push({y,idy});
                }
            }
        }
        // cout<<"ok i="<<i<<endl;
    }
    cout<<ans<<"\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3568kb

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: 3828kb

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: 11ms
memory: 4084kb

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:

011111111111111111100001011000001001110111110111101011011001111110011011101111110111011101001000000101010100111111100110000100110100101101111111110011001111111100100011

result:

wrong answer 1st lines differ - expected: '011111111111111111100001011000...1111111110011001111111100100011', found: '011111111111111111100001011000...1111111110011001111111100100011'