QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#225196 | #7511. Planar Graph | Danilo21 | RE | 32ms | 32628kb | C++17 | 5.1kb | 2023-10-24 04:58:43 | 2023-10-24 04:58:43 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "YES" << en
#define no cout << "NO" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) (__builtin_popcountll(a))
#define bithigh(a) (63-__builtin_clzll(a))
#define lg bithigh
#define highpow(a) (1LL << (ll)lg(a))
using namespace std;
struct Point{
ll x, y;
Point(ll x = 0, ll y = 0){ this->x = x; this->y = y; }
void Read(){ cin >> x >> y; }
Point operator+(const Point& a) const { return Point(x + a.x, y + a.y); }
Point operator-(const Point& a) const { return Point(x - a.x, y - a.y); }
ll operator*(const Point& a) const { return x*a.y - a.x*y; }
static int sig(ll x){ return (x > 0) - (x < 0); }
static bool Intersect(array<Point, 2> a, array<Point, 2> b){
int o1 = sig((a[1] - a[0]) * (b[0] - a[1])) * sig((a[1] - a[0]) * (b[1] - a[1]));
int o2 = sig((b[1] - b[0]) * (a[0] - b[1])) * sig((b[1] - b[0]) * (a[1] - b[1]));
return o1 == -1 && o2 == -1;
}
bool Inside(Point a, Point b, Point c) const {
set<int> s;
s.insert(sig((b - a) * (*this - b)));
s.insert(sig((c - b) * (*this - c)));
s.insert(sig((a - c) * (*this - a)));
s.erase(0);
return s.size() == 1;
}
};
const ll LINF = 4e18;
const int mxN = 1010, INF = 2e9;
ll N, C, n, m, e, e1, comp[mxN*mxN];
Point p[mxN], q[mxN];
array<int, 2> E[mxN], E1[mxN*mxN];
array<int, 3> faces[mxN*mxN];
vector<int> g[mxN*mxN];
bool connected[mxN][mxN], vis[mxN*mxN], has[mxN*mxN];
void AddEdge(int u, int v){
g[u].pb(v);
g[v].pb(u);
}
void dfs(int s, int c){
comp[s] = c;
vis[s] = 1;
for (int u : g[s])
if (!vis[u]) dfs(u, c);
}
void Solve(){
cin >> n >> m >> e;
for (int i = 0; i < n; i++)
p[i].Read();
for (int i = 0; i < m; i++)
q[i].Read();
for (int i = 0; i < e; i++){
cin >> E[i][0] >> E[i][1];
E[i][0]--;
E[i][1]--;
connected[E[i][0]][E[i][1]] = 1;
connected[E[i][1]][E[i][0]] = 1;
}
for (int i = 0; i < n; i++){
for (int j = i+1; j < n; j++){
if (!connected[i][j]){
bool f = 1;
for (int k = 0; k < n; k++)
for (int l = k+1; l < n; l++)
if (i^k && j^k && i^l && j^l && connected[k][l] && Point::Intersect({p[i], p[j]}, {p[k], p[l]}))
f = 0;
if (f){
connected[i][j] = 1;
connected[j][i] = 1;
E1[e1++] = {i, j};
}
}
}
}
for (int i = 0; i < n; i++){
for (int j = i+1; j < n; j++){
if (connected[i][j]){
for (int k = j+1; k < n; k++){
if (connected[i][k] && connected[j][k]){
bool f = 1;
for (int l = 0; l < n; l++)
if (l^i && l^j && l^k && p[l].Inside(p[i], p[j], p[k]))
f = 0;
if (f) faces[N++] = {i, j, k};
}
}
}
}
}
for (int i = 0; i < e1; i++){
vector<int> idx;
for (int j = 0; j < N; j++){
int cnt = 0;
for (int k = 0; k < 3; k++)
if (faces[j][k] == E1[i][0] || faces[j][k] == E1[i][1])
cnt++;
if (cnt == 2) idx.pb(j);
}
if (idx.size() == 1) idx.pb(N);
AddEdge(idx[0], idx[1]);
}
for (int i = 0; i <= N; i++)
if (!vis[i]) dfs(i, C++);
for (int i = 0; i < m; i++){
int idx = N;
for (int j = 0; j < N; j++)
if (q[i].Inside(p[faces[j][0]], p[faces[j][1]], p[faces[j][2]]))
idx = j;
has[comp[idx]] = 1;
}
for (int i = 0; i < e; i++){
vector<int> v;
for (int j = 0; j < N; j++){
int cnt = 0;
for (int k = 0; k < 3; k++)
if (faces[j][k] == E[i][0] || faces[j][k] == E[i][1])
cnt++;
if (cnt == 2) v.pb(comp[j]);
}
if (v.size() == 1) v.pb(comp[N]);
cout << (has[v[0]] || has[v[1]]);
}
cout << en;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0); cerr.tie(0);
cout << setprecision(12) << fixed;
cerr << setprecision(12) << fixed;
cerr << "Started!" << endl;
int t = 1;
//cin >> t;
while (t--)
Solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 31064kb
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: 5ms
memory: 30292kb
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: 11ms
memory: 30272kb
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: 9ms
memory: 30516kb
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: 29ms
memory: 30752kb
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: 26ms
memory: 32628kb
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: 7ms
memory: 32568kb
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: 8ms
memory: 32268kb
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: 7ms
memory: 30488kb
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: 19ms
memory: 27936kb
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: 0
Accepted
time: 11ms
memory: 29632kb
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:
011111111110100110100010010101111011110111010001101101001001111101111111011011011001001001101100100111110111001101101010100100110111100110101010100
result:
ok single line: '011111111110100110100010010101...1010100100110111100110101010100'
Test #12:
score: 0
Accepted
time: 14ms
memory: 32268kb
input:
71 1 142 26 16 -81 21 53 -64 -46 67 -37 73 46 79 66 -27 46 53 38 -44 16 44 -44 -43 -8 -30 65 12 60 2 -26 -24 7 71 -31 -27 -13 0 -80 80 77 -65 71 2 8 -53 -64 -71 52 -58 30 53 61 -18 56 -34 -80 -13 80 56 -28 -79 -43 -52 -38 77 11 -1 -30 -73 -39 30 -61 69 -41 66 16 -45 40 -51 37 40 -26 34 57 29 -15 -8 ...
output:
1000000100000100000000001001000000000010101000000100000011001000000000000001000000000000000000000000000000000000000010011000000000000000000010
result:
ok single line: '100000010000010000000000100100...0000010011000000000000000000010'
Test #13:
score: 0
Accepted
time: 23ms
memory: 27944kb
input:
88 68 244 452074073 749836590 -422267242 -370342423 -649645359 303851355 285738514 -585228292 674035872 344344527 -564943027 45741258 301794983 564572022 349063999 218051130 668851769 598897930 596201080 -750109936 95583385 363387733 130300372 -350613210 -126422550 -684185703 -117024972 -406661982 -...
output:
1111011101010010110011001011101101100000000010100110001111000010001011100110001100101100000010001011101100010000010110111000010101010100101011011101011010011110000111010000011110110111101110011111001111101000110001000110101101001101111100111101
result:
ok single line: '111101110101001011001100101110...1000110101101001101111100111101'
Test #14:
score: 0
Accepted
time: 7ms
memory: 27536kb
input:
24 47 58 -536382548 -36211682 -617682678 630246425 -680303961 -753887401 -576626558 -547501154 -166237320 -247093489 -780629487 -564369462 745821462 -462233962 -29960131 -120134355 -215230222 568441689 -505349805 471834374 -268168811 -773902784 -436226654 -153342090 -686102938 -414449668 -318346027 ...
output:
1011111110101111101111111011101111100110100110101011111011
result:
ok single line: '1011111110101111101111111011101111100110100110101011111011'
Test #15:
score: 0
Accepted
time: 15ms
memory: 31608kb
input:
76 82 181 -835091273 636197461 -809826661 -915012307 -514114180 762992620 -801978217 -646901746 -937647819 -73101245 632623370 -798225996 -949969476 -45929520 677089833 -491546441 -818746494 -457407341 -23609804 -63980274 927682282 -371416961 -936340868 -741789992 -82906350 -740214368 -884276937 -32...
output:
1011111111110100011011111001011110100011001111111001011100111111111110011100101011101011101011111011001100001001110001101110010010101111000101010100111100011011110001100110110110011
result:
ok single line: '101111111111010001101111100101...1100011011110001100110110110011'
Test #16:
score: 0
Accepted
time: 32ms
memory: 31156kb
input:
95 1 39 1 -2 5 -59 6 23 77 57 87 -81 96 -9 20 45 -41 5 -80 -76 62 -83 -26 93 89 -61 -104 -65 55 4 50 55 61 -39 -26 -18 -90 -98 -14 38 56 -61 -100 105 92 -4 30 -98 -13 -27 -21 27 -49 95 62 20 91 24 -75 -30 68 -4 -86 84 -17 -13 -93 13 -38 -64 40 -82 63 47 -9 28 -95 7 91 -51 -50 -66 54 27 -3 -12 -8 -89...
output:
110111101111111110111011111111111111111
result:
ok single line: '110111101111111110111011111111111111111'
Test #17:
score: 0
Accepted
time: 3ms
memory: 32300kb
input:
53 1 95 249310291 444009281 -51319591 -127058272 -521364452 184610945 -21697253 -380031119 -765296404 788815734 480089046 -792178676 285516793 131912022 715950950 -65482217 36211136 -559456984 -46323546 622669323 812068024 -71601366 -6695845 -158750172 23940379 638024824 -792521738 -179875992 -72088...
output:
00000000000010000100000000000100000000000000000000000000000000000000000100000000000000000000000
result:
ok single line: '000000000000100001000000000001...0000000100000000000000000000000'
Test #18:
score: 0
Accepted
time: 24ms
memory: 30808kb
input:
90 87 67 -37 -98 66 -40 17 24 -32 51 -68 56 -47 78 -83 66 -16 -22 41 -12 -31 86 -1 11 42 65 -27 2 -19 -21 -54 78 -14 -77 -74 5 -46 82 -19 63 76 43 -39 -7 62 -49 68 4 -26 72 -91 0 -40 -74 9 -68 92 64 21 88 53 -55 32 -12 100 -26 9 -24 43 -93 -99 19 -76 -3 21 97 -57 -92 -28 26 -10 -95 96 -11 43 -82 22 ...
output:
1111111111111111111111111111110111111111111111111111111111111111111
result:
ok single line: '111111111111111111111111111111...1111111111111111111111111111111'
Test #19:
score: 0
Accepted
time: 3ms
memory: 32572kb
input:
27 42 12 -196639452 -910071469 556979079 -24132720 -907504137 -798429714 217201737 894945050 592735402 -891961813 351726786 -961077191 428253659 -337157490 -814353097 482187973 -746163779 14512669 -639377173 -925754520 -499592664 319782459 -500528351 591167527 -701230268 -495398846 -836405665 445706...
output:
111111111111
result:
ok single line: '111111111111'
Test #20:
score: 0
Accepted
time: 12ms
memory: 31324kb
input:
63 28 102 -65 69 73 -1 0 -30 -69 -66 48 39 3 -37 52 26 13 18 19 -61 -9 54 24 30 -62 58 -64 -64 -6 -3 48 -24 -58 -59 -45 -1 19 -44 64 13 69 -31 38 13 73 -50 -7 -43 4 58 38 56 -21 36 -36 40 -73 17 23 63 -18 63 41 14 47 68 -16 -47 -30 61 -33 43 -45 25 -31 22 -42 2 1 -40 -17 -2 -65 6 21 -58 31 -15 3 -50...
output:
011111100111111110111110011111010010001111111101100111011111111011110101110101011001111111011111111010
result:
ok single line: '011111100111111110111110011111...1110101011001111111011111111010'
Test #21:
score: 0
Accepted
time: 25ms
memory: 32356kb
input:
81 70 214 501181684 467604004 467393962 79858372 -24971604 -76855555 310835183 -451578432 529058882 -371153027 10117013 439009502 -102203223 498873755 104983339 -167287519 -234656041 548196249 -355162848 -403411047 -303715296 -31203991 412378489 -143945211 -38540379 -474967805 -321224760 115499601 -...
output:
0010100000110011101001110011111111000011110110011000110000111111000110011111000001000100111000101111110111101011101110100000001101010100110100011011111111000100110110010100010001101111000101110110010110011010110000
result:
ok single line: '001010000011001110100111001111...1000101110110010110011010110000'
Test #22:
score: -100
Runtime Error
input:
2 1 0 -381381789 -155480688 476986136 269997025 374524257 360034879