# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
401149 | 2021-05-09T13:25:55 Z | idk321 | 늑대인간 (IOI18_werewolf) | C++11 | 546 ms | 91336 KB |
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 200000; vector<int> adj[N]; vector<int> s; vector<int> e; vector<int> l; vector<int> r; vector<int> x; vector<int> y; int n; int q; vector<int> line; int bit[N][20][2]; int bit2[N][20][2]; vector<int> vis[2]; void dfs(int node, int q1, int typ) { if (typ == 0 && node < l[q1]) return; if (typ == 1 && node > r[q1]) return; vis[typ][node] = true; for (int next : adj[node]) { if (vis[typ][next]) continue; dfs(next, q1, typ); } } void cons1() { for (int i = 0; i < n; i++) { bit[i][0][0] = line[i]; bit[i][0][1] = line[i]; } for (int j = 1; j < 20; j++) { for (int i = 0; i + (1 << j) - 1 < n; i++) { bit[i][j][0] = min(bit[i][j - 1][0], bit[i + (1 << (j - 1))][j - 1][0]); bit[i][j][1] = max(bit[i][j - 1][1], bit[i + (1 << (j - 1))][j - 1][1]); } } } void cons2() { for (int i = 0; i < n; i++) { bit2[i][0][0] = line[i]; bit2[i][0][1] = line[i]; } for (int j = 1; j < 20; j++) { for (int i = n - 1; i - (1 << j) + 1 >= 0; i--) { bit2[i][j][0] = min(bit2[i][j - 1][0], bit2[i - (1 << (j - 1))][j - 1][0]); bit2[i][j][1] = max(bit2[i][j - 1][1], bit2[i - (1 << (j - 1))][j - 1][1]); } } } std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,std::vector<int> S, std::vector<int> E,std::vector<int> L, std::vector<int> R) { n = N; x =X; y =Y; s =S; e =E; l = L; r =R; for (int i = 0; i < x.size(); i++) { adj[x[i]].push_back(y[i]); adj[y[i]].push_back(x[i]); } q = S.size(); std::vector<int> res(q); if (n <= 3000 && q <= 3000) { for (int q1 = 0; q1 < q; q1++) { if (s[q1] < l[q1]) { res[q1] = 0; continue; } if (e[q1] > r[q1]) { res[q1] = 0; continue; } vis[0].clear(); vis[0].resize(n); vis[1].clear(); vis[1].resize(n); dfs(s[q1], q1, 0); dfs(e[q1], q1, 1); for (int i = 0; i < n; i++) if (vis[0][i] && vis[1][i]) { res[q1] = 1; } } } vector<int> res2 = res; if (true) { for (int i = 0; i < n; i++) { if (adj[i].size() == 1) { line.push_back(i); break; } } int prev = -1; while (true) { int cnext = - 1; for (int next : adj[line.back()]) { if (next != prev) { cnext = next; } } prev = line.back(); if (cnext == -1) break; line.push_back(cnext); } vector<int> isAt(n); for (int i = 0; i < n; i++) isAt[line[i]] = i; cons1(); cons2(); for (int q1 = 0; q1 < q; q1++) { int a = isAt[s[q1]]; int b = isAt[e[q1]]; if (a < b) { for (int i = 19; i >= 0; i--) { if (a + ((1 << i)) <= n && bit[a][i][0] >= l[q1]) { a += (1 << i); } } for (int i = 19; i >= 0; i--) { if (b - ((1 << i)) >= -1 && bit2[b][i][1] <= r[q1]) { b -= ((1 << i)); } } if (1 + a >= b) res[q1] = 1; } else { swap(a, b); //cout << a << " " << b << endl; for (int i = 19; i >= 0; i--) { if (a + ((1 << i)) <= n && bit[a][i][1] <= r[q1]) { //cout << i << " " << a << " " << bit[a][i][1] << endl; a += (1 << i); } } for (int i = 19; i >= 0; i--) { if (b - ((1 << i)) >= -1 && bit2[b][i][0] >= l[q1]) { //cout << i << " " << b << " " << bit2[b][i][0] << endl; b -= ((1 << i)); } } //cout << a << " " << b << endl; if (1 + a > b) res[q1] = 1; } } } /* for (int i = 0; i< q; i++) { if (res[i] != res2[i]) { cout << s[i] << " a " << e[i] << " " << l[i] << " "<< r[i] << " " << res[i] << " " << res2[i]<< " " << i << endl; } } */ return res; } /* 5 4 1 3 1 1 2 2 0 4 3 1 0 1 0 */
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4940 KB | Output is correct |
2 | Incorrect | 4 ms | 4940 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4940 KB | Output is correct |
2 | Incorrect | 4 ms | 4940 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 546 ms | 91336 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4940 KB | Output is correct |
2 | Incorrect | 4 ms | 4940 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |