| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 293042 |
2020-09-07T15:46:28 Z |
반딧불(#5810) |
ROI16_sending (ROI16_sending) |
C++17 |
|
2552 ms |
54280 KB |
#include <bits/stdc++.h>
#define LIM 20
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
struct Path{
int x, y, idx;
Path(){}
Path(int x, int y, int idx): x(x), y(y), idx(idx){}
bool operator<(const Path &r)const{
if(x != r.x) return x < r.x;
if(y != r.x) return y < r.y;
return idx < r.idx;
}
};
int n, k;
int par[200002];
vector<int> link[200002];
vector<int> centroidChild[200002];
int subTreeSize[200002];
bool centroidUsed[200002];
int centroidRoot;
int ans, ansX=1, ansY=2;
int getSubTreeSize(int x, int par){
subTreeSize[x] = 1;
for(auto &y: link[x]){
if(y == par || centroidUsed[y]) continue;
subTreeSize[x] += getSubTreeSize(y, x);
}
return subTreeSize[x];
}
int findCentroid(int x){
int par = 0;
int treeSize = getSubTreeSize(x, 0);
while(1){
int maxTreeSize = 0, maxTreeIdx = -1;
for(auto &y: link[x]){
if(centroidUsed[y] || y == par) continue;
if(subTreeSize[y] > maxTreeSize) maxTreeSize = subTreeSize[y], maxTreeIdx = y;
}
if(maxTreeSize <= treeSize / 2){
break;
}
par = x;
x = maxTreeIdx;
}
centroidUsed[x] = 1;
for(auto &y: link[x]){
if(centroidUsed[y]) continue;
int tmp = findCentroid(y);
centroidChild[x].push_back(tmp);
}
return x;
}
int group[200002];
int in[200002], inCnt, depth[200002], inIdx[400002];
vector<pair<int, int> > oppVec[200002];
set<pair<int, int> > sets[200002];
int sparse[400002][LIM];
int cover[400002];
void dfsGroup(int x, int groupNum, int p = 0){
group[x] = groupNum;
in[x] = ++inCnt, inIdx[in[x]] = x;
vector<pair<int, int> >().swap(oppVec[x]);
sets[x].clear();
for(auto &y: link[x]){
if(centroidUsed[y] || y==p) continue;
depth[y] = depth[x]+1;
dfsGroup(y, groupNum, x);
inIdx[++inCnt] = x;
}
}
inline int LCAdepth(int x, int y){
x = in[x], y = in[y];
if(x>y) swap(x, y);
int d = cover[y-x];
// return min(sparse[x][d], sparse[y-(1<<d)+1][d]);
int ret = INT_MAX;
for(int i=x; i<=y; i++) ret = min(ret, depth[i]);
return ret;
}
inline void put(int x, pair<int, int> p){
auto it = sets[x].lower_bound(p);
if(it != sets[x].end()){
int tmp = depth[x] + LCAdepth(p.first, it->first);
if(tmp > ans) ans = tmp, ansX = p.second, ansY = it->second;
}
if(it != sets[x].begin()){
it = prev(it);
int tmp = depth[x] + LCAdepth(p.first, it->first);
if(tmp > ans) ans = tmp, ansX = p.second, ansY = it->second;
}
sets[x].insert(p);
}
void dfsCalc(int x, int p = 0){
int maxVal = -1, max_loc = -1;
for(auto &y: link[x]){
if(centroidUsed[y] || y==p) continue;
dfsCalc(y, x);
if(maxVal < (int)sets[y].size()) maxVal = sets[y].size(), max_loc = y;
}
sets[x].swap(sets[max_loc]);
for(auto &y: link[x]){
if(centroidUsed[y] || y==p || y==max_loc) continue;
for(auto p: sets[y]) put(x, p);
sets[y].clear();
}
for(auto p: oppVec[x]){
put(x, p);
}
}
void findAnswer(int c, vector<Path> &ust){
vector<int> nearChild;
vector<vector<pi> > groupVec;
vector<vector<Path> > propVec;
int s;
for(auto &y: link[c]){
if(centroidUsed[y]) continue;
depth[y] = 1; nearChild.push_back(y);
}
centroidUsed[c] = 1;
if(nearChild.empty()) return;
s = (int)nearChild.size();
groupVec.resize(s), propVec.resize(s);
inCnt = depth[c] = 0;
for(int i=0; i<s; i++){
dfsGroup(nearChild[i], i);
inIdx[++inCnt] = c;
}
for(int i=inCnt; i>=1; i--){
sparse[i][0] = depth[inIdx[i]];
for(int j=1; i+(1<<j)<=inCnt; j++){
sparse[i][j] = min(sparse[i][j-1], sparse[i+(1<<(j-1))][j-1]);
}
}
for(auto p: ust){
if(p.x != c && p.y != c && group[p.x] == group[p.y]){
propVec[group[p.x]].push_back(Path(p.x, p.y, p.idx));
continue;
}
if(p.x != c) groupVec[group[p.x]].push_back({in[p.x], p.idx});
if(p.y != c) groupVec[group[p.y]].push_back({in[p.y], p.idx});
if(p.x != c && p.y != c){
oppVec[p.x].push_back({p.y, p.idx});
oppVec[p.y].push_back({p.x, p.idx});
}
}
for(int i=0; i<s; i++){ /// check when common subtree is only one
sort(groupVec[i].begin(), groupVec[i].end());
for(int j=0; j<(int)groupVec[i].size()-1; j++){
int tmp = LCAdepth(inIdx[groupVec[i][j].first], inIdx[groupVec[i][j+1].first]);
if(ans < tmp){
ans = tmp, ansX = groupVec[i][j].second, ansY = groupVec[i][j+1].second;
}
}
for(int j=0; j<(int)groupVec[i].size(); j++){
if(j && groupVec[i][j].first == groupVec[i][j-1].first) continue;
int tmp1 = nearChild[i], tmp2 = inIdx[groupVec[i][j].first];
if(tmp1 != tmp2) propVec[i].push_back(Path(tmp1, tmp2, groupVec[i][j].second));
}
}
/// check when common subtree is two
for(int i=0; i<s; i++){
dfsCalc(nearChild[i]);
}
vector<int>().swap(nearChild);
for(auto &x: groupVec) vector<pi>().swap(x);
vector<vector<pi> >().swap(groupVec);
/// propagate to childs
for(auto &chd: centroidChild[c]){
findAnswer(chd, propVec[group[chd]]);
vector<Path>().swap(propVec[group[chd]]);
}
}
int main(){
for(int i=1; i<=400000; i++) cover[i] = cover[(i-1)/2]+1;
scanf("%d %d", &n, &k);
for(int i=2; i<=n; i++){
scanf("%d", &par[i]);
link[i].push_back(par[i]);
link[par[i]].push_back(i);
}
centroidRoot = findCentroid(1);
memset(centroidUsed, 0, sizeof(centroidUsed));
vector<Path> st;
for(int i=1; i<=k; i++){
int x, y;
scanf("%d %d", &x, &y);
st.push_back(Path(x, y, i));
}
findAnswer(centroidRoot, st);
printf("%d\n%d %d", ans, ansX, ansY);
}
Compilation message
sending.cpp: In function 'int LCAdepth(int, int)':
sending.cpp:87:9: warning: unused variable 'd' [-Wunused-variable]
87 | int d = cover[y-x];
| ^
sending.cpp: In function 'int main()':
sending.cpp:204:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
204 | scanf("%d %d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~
sending.cpp:207:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
207 | scanf("%d", &par[i]);
| ~~~~~^~~~~~~~~~~~~~~
sending.cpp:217:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
217 | scanf("%d %d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 2 |
Correct |
17 ms |
25600 KB |
Output is correct |
| 3 |
Incorrect |
19 ms |
25600 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 2 |
Correct |
17 ms |
25600 KB |
Output is correct |
| 3 |
Incorrect |
19 ms |
25600 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 2 |
Correct |
17 ms |
25600 KB |
Output is correct |
| 3 |
Incorrect |
19 ms |
25600 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 2 |
Correct |
17 ms |
25600 KB |
Output is correct |
| 3 |
Incorrect |
19 ms |
25600 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2552 ms |
54280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1143 ms |
53660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 2 |
Correct |
17 ms |
25600 KB |
Output is correct |
| 3 |
Incorrect |
19 ms |
25600 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 2 |
Correct |
17 ms |
25600 KB |
Output is correct |
| 3 |
Incorrect |
19 ms |
25600 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
