QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#226320#7511. Planar GraphSolitaryDream#WA 1ms3856kbC++173.7kb2023-10-25 20:09:422023-10-25 20:09:43

Judging History

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

  • [2023-10-25 20:09:43]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3856kb
  • [2023-10-25 20:09:42]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 305;
struct P {
    int x, y;
    int Phase() {
        if (y != 0) return y > 0 ? 0 : 1;
        return x > 0 ? 0 : 1;
    }
};
P operator+(P u, P v) { return {u.x + v.x, u.y + v.y}; }
P operator-(P u, P v) { return {u.x - v.x, u.y - v.y}; }
int Det(P u, P v) { return u.x * v.y - u.y * v.x; }
int n, m, e;
P bp[N], sp[N];
P edg_mp[N];
int edg_hs[N][2], sp_hs[N];
vector<pii> g[N];
inline int Intersect(P x, P u, P v) {
    if ((u - x).Phase() == (v - x).Phase()) return 0;
    if ((u - x).Phase() == 0) swap(u, v);
    return Det(v - u, x - u) > 0;
}
inline int Inside(P cur, const vector<P> &pts) {
    int area = 0;
    for (int i = 0; i + 1 < pts.size(); ++i) area += Det(pts[i], pts[i + 1]);
    int cnt = (area <= 0 ? 1 : 0);
    for (int j = 0; j + 1 < pts.size(); ++j) {
        if (Intersect(cur, pts[j], pts[j + 1])) ++cnt;
    }
    return cnt & 1;
}
mt19937 rd(1025);
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> e;
    for (int i = 1; i <= n; ++i) {
        cin >> bp[i].x >> bp[i].y;
        bp[i].x *= 2; bp[i].y *= 2;
    }
    for (int i = 1; i <= m; ++i) {
        cin >> sp[i].x >> sp[i].y;
        sp[i].x *= 2; sp[i].y *= 2;
    }
    for (int i = 0, x, y; i < e; ++i) {
        cin >> x >> y;
        g[x].push_back({y, i << 1});
        g[y].push_back({x, i << 1 | 1});
        edg_mp[i] = bp[x] + bp[y];
        edg_mp[i].x /= 2; edg_mp[i].y /= 2;
    }
    for (int i = 1; i <= n; ++i) {
        sort(g[i].begin(), g[i].end(), [&](pii u, pii v) {
            P vecu = bp[u.first] - bp[i];
            P vecv = bp[v.first] - bp[i];
            int du = vecu.Phase();
            int dv = vecv.Phase();
            if (du != dv) return du < dv;
            return Det(vecu, vecv) > 0;
        });
    }
    vector<int> vis(e << 1);
    for (int x = 1, ts = 0; x <= n; ++x) {
        for (auto [y, id] : g[x]) if (!vis[id]) {
            ++ts;
            vector<P> pts(2);
            vector<int> eds(1);
            pts[0] = bp[x]; pts[1] = bp[y]; 
            eds[0] = id;
            vis[id] = ts;
            for (int nx = y, la = x, la_id = id; ; ) {
                int k = find(g[nx].begin(), g[nx].end(), pii(la, la_id ^ 1)) - g[nx].begin();
                k = (k + g[nx].size() - 1) % g[nx].size();
                auto [nnx, nid] = g[nx][k];
                vis[nid] = ts;
                eds.push_back(nid);
                pts.push_back(bp[nnx]);
                if (nnx == x) break;
                la = nx; nx = nnx; la_id = nid; 
            }
            // for (auto [x, y] : pts) cerr << "(" << x << ' ' << y << ')';
            // cerr << endl;
            int cur_hash = rd();
            for (int i = 1; i <= m; ++i) if (Inside(sp[i], pts)) sp_hs[i] ^= cur_hash;
            for (int i = 0; i < e; ++i) {
                bool is_on = 0;
                if (vis[i << 1] == ts) {
                    is_on = 1;
                    edg_hs[i][0] ^= cur_hash;
                }
                if (vis[i << 1 | 1] == ts) {
                    is_on = 1;
                    edg_hs[i][1] ^= cur_hash;   
                }
                if (!is_on && Inside(edg_mp[i], pts)) {
                    edg_hs[i][0] ^= cur_hash;
                    edg_hs[i][1] ^= cur_hash;
                }
            }
        }
    }
    set<int> st;
    for (int i = 1; i <= m; ++i) st.insert(sp_hs[i]);
    string ans(e, '0');
    for (int i = 0; i < e; ++i) if (st.count(edg_hs[i][0]) || st.count(edg_hs[i][1])) ans[i] = '1';
    cout << ans << endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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

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

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: 1ms
memory: 3580kb

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

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:

01110111111111111110101110111011101111110011100110100111110110001110111101100111100111010111111110110101110111110011111001110001111100010111110111111111

result:

ok single line: '011101111111111111101011101110...1110001111100010111110111111111'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

62 1 99
-72 -45
-58 -44
-39 5
-45 -56
11 -26
-7 56
-29 -56
-70 -26
64 -64
-12 6
4 44
-14 68
-28 29
-68 -52
-21 -10
19 -37
17 -30
26 64
-40 2
-11 -30
64 -45
38 -67
43 -35
67 -49
50 72
-60 -2
-28 37
55 55
-7 42
-63 -32
71 35
-55 26
-67 -49
-42 -43
69 59
-29 5
0 -36
-1 8
-53 66
1 -6
-2 32
-51 -61
-27 6...

output:

000010000000000110001101000110000000010010000001001001100000010010000010001100010011010101001000010

result:

ok single line: '000010000000000110001101000110...0010001100010011010101001000010'

Test #9:

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

input:

63 1 175
50549954 -224104196
-187903718 57327090
-61398050 89271831
72686467 -167765054
4226095 73332567
-80682032 -158732552
-366425325 -180661648
-210787891 -107411752
44235201 233049038
-29484914 -280845598
228925315 -106736012
-169221325 64453690
-127160591 78410226
374001485 -312357450
31528300...

output:

0000000100000000000000000000000000010000000000000000000001000000000000000010000000000000000000000000000000000010000000000000010000000000000001000000000100000101000000000001000

result:

ok single line: '000000010000000000000000000000...0000000100000101000000000001000'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

82 4 66
182782804 77923360
117828203 139218692
-110620000 89777361
273011388 138341008
294610527 -194481138
294204618 -290402347
194417551 48839146
-161919200 -261350494
-260772975 -239789170
117370125 245536520
-201599590 -82451402
291486591 84106590
296266013 309943147
-220542664 54399074
24021444...

output:

111101011111111111111111010111111101010111100110100011111111011111

result:

ok single line: '111101011111111111111111010111...1010111100110100011111111011111'

Test #11:

score: -100
Wrong Answer
time: 0ms
memory: 3664kb

input:

65 50 147
-581452360 190355182
-642896619 -572084384
-305018177 -539060586
-328404608 -74526018
198824769 -402666976
-604806291 420433161
646918331 -591294299
360443372 -456307852
253325248 -341024549
-656241212 302363402
524405246 -499973260
-531933602 617077471
-185233072 -318131117
-362315669 -49...

output:

011111110110100110100000010101111011110001010001101101001001001101111111010011011001001001101100100111110111000101100000000100000011100100101010100

result:

wrong answer 1st lines differ - expected: '011111111110100110100010010101...1010100100110111100110101010100', found: '011111110110100110100000010101...0000000100000011100100101010100'