| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1037704 |
2024-07-29T07:04:14 Z |
정민찬(#10982) |
Tourism (JOI23_tourism) |
C++17 |
|
796 ms |
68588 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const int inf = 2e9;
int N, M, Q;
vector<int> adj[100010];
int C[100010];
vector<int> s[100010];
int L[100010];
int R[100010];
int ans[100010];
int dia[100010];
int chk[100010];
int sz[100010];
int getSize(int x, int p) {
sz[x] = 1;
for (auto &y : adj[x]) {
if (y == p || chk[y]) continue;
sz[x] += getSize(y, x);
}
return sz[x];
}
int getCent(int x, int p, int cap) {
for (auto &y : adj[x]) {
if (y == p || chk[y]) continue;
if (sz[y] * 2 > cap) return getCent(y, x, cap);
}
return x;
}
struct Fenwick{
vector<int> tree;
void init(int n) {
tree.assign(n+1, 0);
}
void upd(int i, int v, int n) {
while (i <= n) {
tree[i] += v;
i += i & -i;
}
}
int qry(int i) {
int ret = 0;
while (i) {
ret += tree[i];
i -= i & -i;
}
return ret;
}
int qry(int l, int r) {
return qry(r) - qry(l-1);
}
};
struct MaxSegmentTree{
vector<pair<int,int>> tree;
void init(int n) {
int sz = 1 << __lg(n-1) + 2;
tree.resize(sz);
build(1, 1, n);
}
void build(int node, int s, int e) {
if (s == e) {
tree[node] = {-inf, s};
return;
}
int mid = s + e >> 1;
build(node*2, s, mid);
build(node*2+1, mid+1, e);
tree[node] = max(tree[node*2], tree[node*2+1]);
}
void update(int node, int s, int e, int tar, int val, int num = -1) {
if (s > tar || tar > e) return;
if (s == e) {
if (num == -1) num = s;
tree[node] = {val, num};
return;
}
int mid = s + e >> 1;
update(node*2, s, mid, tar, val, num);
update(node*2+1, mid+1, e, tar, val, num);
tree[node] = max(tree[node*2], tree[node*2+1]);
}
pair<int,int> query(int node, int s, int e, int l, int r) {
if (l > e || s > r) return {-inf, -1};
if (l <= s && e <= r) return tree[node];
int mid = s + e >> 1;
return max(query(node*2, s, mid, l, r), query(node*2+1, mid+1, e, l, r));
}
};
Fenwick seg;
MaxSegmentTree mxs, mns;
vector<int> D;
int Idx(int v) {
return lower_bound(D.begin(), D.end(), v) - D.begin() + 1;
}
void dfs(int x, int p) {
for (auto &k : s[x]) {
D.push_back(k);
}
for (auto &y : adj[x]) {
if (y == p || chk[y]) continue;
dfs(y, x);
}
}
void dfs2(int x, int p, int r) {
for (auto &k : s[x]) {
int idx = Idx(k);
mxs.update(1, 1, D.size(), idx, r);
mns.update(1, 1, D.size(), idx, -r);
}
for (auto &y : adj[x]) {
if (y == p || chk[y]) continue;
dfs2(y, x, r);
}
}
void dfs3(int x, int p, int dep, int r) {
for (auto &k : s[x]) {
int idx = Idx(k);
mxs.update(1, 1, D.size(), idx, dep, r);
}
for (auto &y : adj[x]) {
if (y == p || chk[y]) continue;
dfs3(y, x, dep+1, r);
}
}
void dfs3_del(int x, int p) {
for (auto &k : s[x]) {
int idx = Idx(k);
mxs.update(1, 1, D.size(), idx, -inf);
}
for (auto &y : adj[x]) {
if (y == p || chk[y]) continue;
dfs3_del(y, x);
}
}
int getSize2(int x, int p) {
sz[x] = s[x].size();
for (auto &y : adj[x]) {
if (y == p || chk[y]) continue;
sz[x] += getSize2(y, x);
}
return sz[x];
}
set<int> ss[100010];
int id[100010];
int pv;
vector<pair<int,int>> save[100010];
void my_ins(int i, int k, int cnt, int x) {
auto rit = ss[i].lower_bound(k);
if (rit != ss[i].end()) {
save[k+1].push_back({*rit, cnt});
}
if (rit != ss[i].begin()) {
auto lit = prev(rit);
save[*lit+1].push_back({k, cnt});
if (rit != ss[i].end()) {
save[*lit+1].push_back({*rit, -cnt});
}
}
ss[i].insert(k);
}
int dfs4(int x, int p, int cnt) {
int mxsz = -1, ch = -1;
for (auto &y : adj[x]) {
if (y == p || chk[y]) continue;
if (sz[y] > mxsz) {
mxsz = sz[y];
ch = y;
}
}
if (ch == -1) {
id[x] = pv ++;
int p = 0;
ss[id[x]].insert(0);
for (auto &k : s[x]) {
ss[id[x]].insert(Idx(k));
save[p+1].push_back({Idx(k), cnt});
p = Idx(k);
}
return id[x];
}
else {
id[x] = dfs4(ch, x, cnt + 1);
for (auto &y : adj[x]) {
if (y == p || y == ch || chk[y]) continue;
int z = dfs4(y, x, 1);
for (auto &k : ss[z]) {
if (k == 0) continue;
my_ins(id[x], Idx(k), cnt, x);
}
}
for (auto &k : s[x]) {
my_ins(id[x], Idx(k), cnt, x);
}
return id[x];
}
}
void dnc(int x, vector<int> qrs) {
if (qrs.empty()) return;
x = getCent(x, -1, getSize(x, -1));
D.clear();
dfs(x, -1);
sort(D.begin(), D.end());
mxs.init(D.size()); mns.init(D.size());
for (int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if (chk[y]) continue;
dfs2(y, x, i);
}
for (auto &k : s[x]) {
int idx = Idx(k);
mxs.update(1, 1, D.size(), idx, -1);
mns.update(1, 1, D.size(), idx, 1);
}
vector<int> curq;
vector<int> nxtq[adj[x].size()];
for (auto &i : qrs) {
int li = Idx(L[i]), ri = Idx(R[i]);
int ret1 = mxs.query(1, 1, D.size(), li, ri).first;
int ret2 = -mns.query(1, 1, D.size(), li, ri).first;
if (ret1 == ret2 && ret1 != -1) {
nxtq[ret1].push_back(i);
}
else {
curq.push_back(i);
}
}
mxs.init(D.size());
for (int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if (chk[y]) continue;
dfs3(y, x, 1, i);
}
vector<int> mxi[adj[x].size()];
for (auto &i : curq) {
if (L[i] == R[i]) dia[i] = 0;
else {
pair<int,int> ret = mxs.query(1, 1, D.size(), Idx(L[i]), Idx(R[i]));
dia[i] = ret.first;
mxi[ret.second].push_back(i);
}
}
for (int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if (chk[y]) continue;
dfs3_del(y, x);
for (auto &j : mxi[i]) {
dia[j] += max(0, mxs.query(1, 1, D.size(), Idx(L[j]), Idx(R[j])).first);
}
dfs3(y, x, 1, i);
}
getSize2(x, -1);
pv = 0;
dfs4(x, -1, 0);
for (int i=0; i<pv; i++) {
ss[i].clear();
}
seg.init(D.size());
sort(curq.begin(), curq.end(), [&] (int &u, int &v) { return L[u] < L[v]; });
int j = 0;
for (int i=1; i<=D.size(); i++) {
for (auto &[pos, v] : save[i]) {
seg.upd(pos, v, D.size());
}
while (j < curq.size() && L[curq[j]] == D[i-1]) {
ans[curq[j]] = seg.qry(Idx(L[curq[j]]), Idx(R[curq[j]]));
j ++;
}
}
for (int i=0; i<=D.size() + 2; i++) {
save[i].clear();
}
chk[x] = 1;
for (int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if (chk[y]) continue;
dnc(y, nxtq[i]);
}
}
int main() {
ios_base :: sync_with_stdio(false); cin.tie(NULL);
cin >> N >> M >> Q;
for (int i=0; i<N-1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i=1; i<=M; i++) {
cin >> C[i];
s[C[i]].push_back(i);
}
for (int i=1; i<=Q; i++) {
cin >> L[i] >> R[i];
}
vector<int> Sum(N+1, 0);
for (int i=1; i<=N; i++) {
sort(s[i].begin(), s[i].end());
Sum[i] = Sum[i-1] + s[i].size();
}
vector<int> initq(Q);
iota(initq.begin(), initq.end(), 1);
dnc(1, initq);
for (int i=1; i<=Q; i++) {
cout << ans[i] + 1 << '\n';
}
}
Compilation message
tourism.cpp: In member function 'void MaxSegmentTree::init(int)':
tourism.cpp:66:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
66 | int sz = 1 << __lg(n-1) + 2;
| ~~~~~~~~~~^~~
tourism.cpp: In member function 'void MaxSegmentTree::build(int, int, int)':
tourism.cpp:75:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
75 | int mid = s + e >> 1;
| ~~^~~
tourism.cpp: In member function 'void MaxSegmentTree::update(int, int, int, int, int, int)':
tourism.cpp:87:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
87 | int mid = s + e >> 1;
| ~~^~~
tourism.cpp: In member function 'std::pair<int, int> MaxSegmentTree::query(int, int, int, int, int)':
tourism.cpp:95:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
95 | int mid = s + e >> 1;
| ~~^~~
tourism.cpp: In function 'void dnc(int, std::vector<int>)':
tourism.cpp:227:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
227 | for (int i=0; i<adj[x].size(); i++) {
| ~^~~~~~~~~~~~~~
tourism.cpp:251:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
251 | for (int i=0; i<adj[x].size(); i++) {
| ~^~~~~~~~~~~~~~
tourism.cpp:265:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
265 | for (int i=0; i<adj[x].size(); i++) {
| ~^~~~~~~~~~~~~~
tourism.cpp:283:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
283 | for (int i=1; i<=D.size(); i++) {
| ~^~~~~~~~~~
tourism.cpp:287:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
287 | while (j < curq.size() && L[curq[j]] == D[i-1]) {
| ~~^~~~~~~~~~~~~
tourism.cpp:292:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
292 | for (int i=0; i<=D.size() + 2; i++) {
| ~^~~~~~~~~~~~~~
tourism.cpp:296:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
296 | for (int i=0; i<adj[x].size(); i++) {
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
15196 KB |
Output is correct |
| 2 |
Correct |
2 ms |
15196 KB |
Output is correct |
| 3 |
Correct |
2 ms |
15196 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
15420 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
15196 KB |
Output is correct |
| 2 |
Correct |
2 ms |
15196 KB |
Output is correct |
| 3 |
Correct |
2 ms |
15196 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
15420 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
15196 KB |
Output is correct |
| 2 |
Runtime error |
11 ms |
30812 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
15196 KB |
Output is correct |
| 2 |
Correct |
229 ms |
43196 KB |
Output is correct |
| 3 |
Correct |
399 ms |
59600 KB |
Output is correct |
| 4 |
Correct |
294 ms |
50636 KB |
Output is correct |
| 5 |
Correct |
518 ms |
67548 KB |
Output is correct |
| 6 |
Correct |
556 ms |
68324 KB |
Output is correct |
| 7 |
Correct |
518 ms |
67736 KB |
Output is correct |
| 8 |
Correct |
534 ms |
65988 KB |
Output is correct |
| 9 |
Correct |
501 ms |
67524 KB |
Output is correct |
| 10 |
Correct |
567 ms |
68164 KB |
Output is correct |
| 11 |
Correct |
495 ms |
66500 KB |
Output is correct |
| 12 |
Correct |
569 ms |
68588 KB |
Output is correct |
| 13 |
Incorrect |
796 ms |
67848 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
15196 KB |
Output is correct |
| 2 |
Runtime error |
12 ms |
30808 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
15196 KB |
Output is correct |
| 2 |
Correct |
2 ms |
15196 KB |
Output is correct |
| 3 |
Correct |
2 ms |
15196 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
15420 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
