QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#305773#7511. Planar GraphELDRVDWA 1ms6340kbC++143.6kb2024-01-15 23:38:172024-01-15 23:38:18

Judging History

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

  • [2024-01-15 23:38:18]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6340kb
  • [2024-01-15 23:38:17]
  • 提交

answer

//https://qoj.ac/contest/1376/problem/7511
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define PI acos(-1)
#define LSB(i) ((i) & -(i))
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define sc second
#define th third
#define fo fourth
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ldb double
#define INF 1e15
#define MOD 1000000007
#define endl "\n"

#define all(data)       data.begin(),data.end()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()
#define MAXN 307
#define MAXN3 10000007
#define MAXM 10007
struct pt {ll x, y;};
pt a[MAXN],b[MAXN];
vector<ll> adj[MAXM],v,v1[MAXM],v2[MAXM];
vector<pll> vv;
ll edge[MAXN][MAXN],rez[MAXN],cnt,bl=1;
bool vis[MAXN3];
ll cross(pt a,pt b,pt c)
{
	ll r=(c.x-a.x)*(b.y-a.y)-(c.y-a.y)*(b.x-a.x);
	if(r>0) return 1;
	else if(r<0) return -1;
	return 0;
}
bool Secivajuse(pt a,pt b,pt c,pt d)
{
	if(cross(a,b,d)==0 || cross(a,b,c)==0 || cross(a,d,c)==cross(a,b,d)) return false;
	if(cross(c,d,a)==0 || cross(c,d,b)==0 || cross(c,d,a)==cross(c,d,b)) return false;
	return true;
}
void DFS(ll i)
{
    vis[i]=true;
    for(auto j:adj[i])
    {
        if(!vis[j]) DFS(j);
    }
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
    ll n,m,e,mm,dd; cin>>n>>m>>e;
    for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
    for(int i=1;i<=m;i++) cin>>b[i].x>>b[i].y;
    for (int i=1;i<=e;i++)
    {
    	cin>>mm>>dd; vv.pb({mm,dd});
    	edge[mm][dd]=edge[dd][mm]=i;
    }
    if(!e) return 0;
    for(int i=1;i<n;i++)
    {
    	for(int j=i+1;j<=n;j++)
    	{
    		if(edge[i][j]) continue;
    		bool check=true;
    		for(auto u:vv)
            {
                if(Secivajuse(a[i],a[j],a[u.fi],a[u.sc])) {check=false; break;}
            }
    		if(check) {vv.pb({i,j}); edge[i][j]=edge[j][i]=vv.size();}
    	}
    }
   	for(int i=1;i<n-1;i++)
    {
   		for(int j=i+1;j<n;j++)
   		{
   			for(int k=j+1;k<=n;k++)
   			{
   				if(!edge[i][j] || !edge[j][k] || !edge[k][i]) continue;
   				bool check=false;
   				for(int l=1;l<=n;l++)
   				{
                    if(cross(a[i],a[j],a[l])==cross(a[k],a[i],a[l]) && cross(a[j],a[k],a[l])==cross(a[k],a[i],a[l])) {check=true; break;}
   				}
   				if(check) continue;
   				v1[bl].pb(edge[i][j]); v1[bl].pb(edge[j][k]); v1[bl].pb(edge[k][i]);
   				v2[edge[i][j]].pb(bl); v2[edge[j][k]].pb(bl); v2[edge[k][i]].pb(bl);
   				bool checkk=false;
   				for(int l=1;l<=m;l++)
                {
					if(cross(a[i],a[j],a[l])==cross(a[k],a[i],a[l]) && cross(a[j],a[k],a[l])==cross(a[k],a[i],a[l])) {checkk=true; cnt++;}
   				}
   				if(checkk) v.pb(bl);
   				bl++;
   			}
   		}
   	}
   	if(cnt!=m) v.pb(bl);
   	for(int i=e+1;i<=vv.size();i++)
    {
   		if(v2[i].size()==2)
   		{
   			adj[v2[i].front()].pb(v2[i].back());
   			adj[v2[i].back()].pb(v2[i].front());
   		}
   		else
   		{
   			adj[v2[i].front()].pb(bl);
   			adj[bl].pb(v2[i].front());
   		}
   	}
   	for(auto i:v)
    {
   		if(!vis[i]) DFS(i);
   	}
   	for(int i=1;i<bl;i++)
    {
        if(vis[i])
        {
            for(auto j:v1[i]) rez[i]=(ll)(i<=e);
        }
    }
    if(vis[bl])
   	{
   		for(int i=1;i<=e;i++)
   		{
   			if(v2[i].size()==1) rez[i]=1;
   		}
   	}
   	for(int i=1;i<=e;i++) cout<<rez[i];
   	return 0;
}
/*
4 1 3
-2 0
0 2
2 0
0 1
0 3
1 2
2 3
1 3
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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:

1111100010011

result:

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