QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#297743#7511. Planar Graphsofija6WA 2ms3896kbC++235.7kb2024-01-05 05:54:412024-01-05 05:54:41

Judging History

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

  • [2024-01-05 05:54:41]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3896kb
  • [2024-01-05 05:54:41]
  • 提交

answer

#include <bits/stdc++.h>
#define ll int
#define MAXN 110
using namespace std;
struct point
{
    ll X,Y;
};
struct segment
{
    point A,B;
};
struct triangle
{
    ll iA,iB,iC;
};
point b[MAXN],s[MAXN];
vector<pair<ll,ll> > lines,out;
ll n,m,e,p[3*MAXN],q[3*MAXN],edge[MAXN][MAXN],ind,ans[3*MAXN];
vector<ll> G[MAXN*MAXN];
bool has[MAXN*MAXN],V[MAXN*MAXN];
ll Cross(point c,point b,point a)
{
    ll val=(b.X-c.X)*(a.Y-c.Y)-(b.Y-c.Y)*(a.X-c.X);
    if (val>0)
        return 1;
    if (val<0)
        return -1;
    return 0;
}
bool Same_Points(point a,point b)
{
    return (a.X==b.X && a.Y==b.Y);
}
bool Intersect(segment a,segment b)
{
    if (Same_Points(a.A,b.A) || Same_Points(a.A,b.B) || Same_Points(a.B,b.A) || Same_Points(a.B,b.B))
        return false;
    return (Cross(a.A,a.B,b.A)!=Cross(a.A,a.B,b.B) && Cross(b.A,b.B,a.A)!=Cross(b.A,b.B,a.B));
}
void Draw_Lines()
{
    for (ll i=1;i<=n;i++)
    {
        for (ll j=i+1;j<=n;j++)
        {
            if (edge[i][j])
                continue;
            bool yes=true;
            for (ll l=1;l<lines.size();l++)
            {
                pair<ll,ll> k=lines[l];
                if (Intersect({b[i],b[j]},{b[k.first],b[k.second]}))
                {
                    yes=false;
                    break;
                }
            }
            if (yes)
            {
                edge[i][j]=lines.size();
                edge[j][i]=lines.size();
                lines.push_back({i,j});
            }
        }
    }
}
vector<triangle> t;
bool Check(ll i,ll j,ll k)
{
    for (ll l=1;l<=n;l++)
    {
        if (i==l || j==l || k==l)
            continue;
        if (Cross(b[i],b[j],b[l])==Cross(b[j],b[k],b[l]) && Cross(b[i],b[j],b[l])==Cross(b[k],b[i],b[l]))
            return false;
    }
    return true;
}
void Get_Triangles()
{
    for (ll i=1;i<=n;i++)
    {
        for (ll j=i+1;j<=n;j++)
        {
            for (ll k=j+1;k<=n;k++)
            {
                if (edge[i][j] && edge[j][k] && edge[k][i] && Check(i,j,k))
                    t.push_back({i,j,k});
            }
        }
    }
}
void Get_Out_Lines()
{
    for (ll l=1;l<lines.size();l++)
    {
        pair<ll,ll> i=lines[l];
        ll cur=0;
        bool yes=true;
        for (ll j=1;j<=n;j++)
        {
            if (j==i.first || j==i.second)
                continue;
            if (!cur)
                cur=Cross(b[i.first],b[i.second],b[j]);
            else if (cur!=Cross(b[i.first],b[i.second],b[j]))
            {
                yes=false;
                break;
            }
        }
        if (yes)
            out.push_back(i);
    }
}
void Create_Graph()
{
    map<ll,vector<ll> > mp;
    for (ll i=1;i<t.size();i++)
    {
        ll a=t[i].iA,b=t[i].iB,c=t[i].iC;
        if (edge[a][b]>e)
            mp[edge[a][b]].push_back(i);
        if (edge[b][c]>e)
            mp[edge[b][c]].push_back(i);
        if (edge[c][a]>e)
            mp[edge[c][a]].push_back(i);
    }
    for (auto i : mp)
    {
        if (i.second.size()==1)
        {
            G[ind].push_back(i.second[0]);
            G[i.second[0]].push_back(ind);
        }
        else
        {
            G[i.second[1]].push_back(i.second[0]);
            G[i.second[0]].push_back(i.second[1]);
        }
    }
}
void Contains_Source()
{
    bool in[m+2]={false};
    for (ll i=1;i<t.size();i++)
    {
        ll aa=t[i].iA,bb=t[i].iB,cc=t[i].iC;
        for (ll j=1;j<=m;j++)
        {
            ll c1=Cross(b[aa],b[bb],s[j]),c2=Cross(b[bb],b[cc],s[j]),c3=Cross(b[cc],b[aa],s[j]);
            set<ll> ss;
            ss.insert(c1);
            ss.insert(c2);
            ss.insert(c3);
            if (ss.count(0))
                ss.erase(0);
            if (ss.size()==1)
            {
                in[j]=true;
                has[i]=true;
            }
        }
    }
    for (ll i=1;i<=m;i++)
    {
        if (!in[i])
            has[ind]=true;
    }
}
void Solve()
{
    queue<ll> q;
    for (ll i=1;i<=ind;i++)
    {
        if (has[i])
        {
            q.push(i);
            V[i]=true;
        }
    }
    while (!q.empty())
    {
        ll i=q.front();
        q.pop();
        for (ll next : G[i])
        {
            if (!V[next])
            {
                q.push(next);
                V[next]=true;
            }
        }
    }
    for (ll i=1;i<ind;i++)
    {
        if (V[i])
        {
            ll aa=t[i].iA,bb=t[i].iB,cc=t[i].iC;
            if (edge[aa][bb]<=e)
                ans[edge[aa][bb]]=true;
            if (edge[cc][bb]<=e)
                ans[edge[cc][bb]]=true;
            if (edge[aa][cc]<=e)
                ans[edge[aa][cc]]=true;
        }
    }
    if (V[ind])
    {
        for (auto i : out)
        {
            ll aa=i.first,bb=i.second;
            if (edge[aa][bb]<=e)
                ans[edge[aa][bb]]=true;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> e;
    for (ll i=1;i<=n;i++)
        cin >> b[i].X >> b[i].Y;
    for (ll i=1;i<=m;i++)
        cin >> s[i].X >> s[i].Y;
    lines.push_back({0,0});
    t.push_back({0,0,0});
    out.push_back({0,0});
    for (ll i=1;i<=e;i++)
    {
        cin >> p[i] >> q[i];
        lines.push_back({p[i],q[i]});
        edge[p[i]][q[i]]=i;
        edge[q[i]][p[i]]=i;
    }
    Draw_Lines();
    Get_Triangles();
    Get_Out_Lines();
    ind=t.size();
    Create_Graph();
    Contains_Source();
    Solve();
    for (ll i=1;i<=e;i++)
        cout << ans[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: 3800kb

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

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: 0
Accepted
time: 1ms
memory: 3896kb

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:

011111111111111111100001011000001001110111110111101011011001111110011011101111110111011101001000000001010100111111100110000100110100101101111111110011001111111100100011

result:

ok single line: '011111111111111111100001011000...1111111110011001111111100100011'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

59 1 158
-51 8
50 48
-56 -67
19 7
33 -47
32 44
42 47
-36 -57
15 34
-8 23
-24 43
20 11
61 -41
58 -11
-68 -45
36 -54
-21 42
-28 -49
-28 -31
-34 20
29 -65
-13 38
-22 -36
-30 11
-40 57
64 -69
65 51
47 34
-41 31
-1 35
28 -11
58 58
13 12
-52 43
40 6
46 48
46 -59
-52 30
69 -23
-34 38
-1 -5
-12 -27
-11 24
-...

output:

00000000000000000000000000000000000000000000000000000000000001000000000000000000000000000001000000000000000000000000000000000000000000000000001000000000000000

result:

ok single line: '000000000000000000000000000000...0000000000000001000000000000000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3820kb

input:

92 1 125
55 10
67 -85
-26 80
36 -32
44 -64
41 -50
-93 -80
-66 -92
-68 27
-79 9
87 -61
-40 -64
89 100
75 -42
59 40
60 -30
-66 27
63 90
-19 100
24 -20
-13 83
-100 -92
-83 58
-33 -70
74 -20
-55 73
-41 28
27 -31
-37 -22
40 18
-3 -2
70 79
71 29
32 -73
39 -1
17 -95
-61 56
94 -10
-79 -66
-84 87
-16 71
52 4...

output:

10010010000101001010010100101100100000001010001000000001101111101000011111000000001011000100000010100000000100011011000000110

result:

ok single line: '100100100001010010100101001011...0010100000000100011011000000110'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3840kb

input:

85 47 204
48 93
-32 10
71 70
-37 10
20 -12
-32 -56
1 -22
-46 -64
56 82
-19 63
-5 83
16 89
79 81
51 -22
43 59
33 -87
28 67
-18 38
-16 -23
18 -78
87 66
-83 29
36 58
6 -2
68 80
18 -34
-17 59
-31 -12
-37 -75
33 -79
-51 -24
-88 6
-19 62
71 -78
-51 72
-49 -45
21 41
-58 33
46 67
-11 -31
62 46
54 55
37 -14
...

output:

000110010001001101100010110101100100011110011110110101010100110011111010101110101001001011100000110101000100010011100100100110100001011010001010001010000100011000001101010110011001101111010000011001000011

result:

ok single line: '000110010001001101100010110101...0011001101111010000011001000011'

Test #7:

score: -100
Wrong Answer
time: 1ms
memory: 3892kb

input:

59 96 152
-75886847 147807525
335545968 317138952
262969730 -308175740
91308409 -162085508
-397786268 -191693417
-227565597 195627938
45666011 253210394
-311142459 58197832
-412164189 -270215767
-12639523 -314154358
-269901472 -366179516
-306681757 -167771007
194329800 -339296479
-12501616 -15788817...

output:

00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

result:

wrong answer 1st lines differ - expected: '011101111111111111101011101110...1110001111100010111110111111111', found: '000000000000000000000000000000...0000000000000000000000000000000'