QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#226320 | #7511. Planar Graph | SolitaryDream# | WA | 1ms | 3856kb | C++17 | 3.7kb | 2023-10-25 20:09:42 | 2023-10-25 20:09:43 |
Judging History
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;
}
詳細信息
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'