| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 292842 |
2020-09-07T14:10:34 Z |
반딧불(#5810) |
ROI16_sending (ROI16_sending) |
C++17 |
|
363 ms |
116592 KB |
#include <bits/stdc++.h>
#define LIM 18
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 par = 0){
group[x] = groupNum;
in[x] = ++inCnt, inIdx[in[x]] = x;
oppVec[x].clear(), sets[x].clear();
for(auto &y: link[x]){
if(centroidUsed[y] || y==par) 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]);
}
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 par = 0){
int minVal = INT_MAX, min_loc = -1;
for(auto &y: link[x]){
if(centroidUsed[y] || y==par) continue;
dfsCalc(y, x);
if(minVal > (int)sets[y].size()) minVal = sets[y].size(), min_loc = y;
}
sets[x] = sets[min_loc];
for(auto &y: link[x]){
if(centroidUsed[y] || y==par || y==min_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);
}
if(nearChild.empty()) return;
centroidUsed[c] = 1;
s = (int)nearChild.size();
groupVec.resize(s), propVec.resize(s);
inCnt = 0;
for(int i=0; i<s; i++){
dfsGroup(nearChild[i], i);
}
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(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){ /// insert into map
int tmp1 = group[p.x], tmp2 = group[p.y];
if(tmp1 > tmp2) swap(tmp1, tmp2);
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 tmpMin = INT_MAX;
for(int x=groupVec[i][j].first; x<=groupVec[i][j+1].first; x++) tmpMin = min(tmpMin, depth[inIdx[x]]);
if(ans < tmpMin){
ans = tmpMin, 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];
propVec[i].push_back(Path(min(tmp1, tmp2), max(tmp1, tmp2), groupVec[i][j].second));
}
}
/// check when common subtree is two
for(int i=0; i<s; i++){
dfsCalc(nearChild[i], 0);
}
/// propagate to childs
for(auto &chd: centroidChild[c]){
findAnswer(chd, 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(min(x, y), max(x, y), i));
}
findAnswer(centroidRoot, st);
printf("%d\n%d %d", ans, ansX, ansY);
}
Compilation message
sending.cpp: In function 'int main()':
sending.cpp:196:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
196 | scanf("%d %d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~
sending.cpp:198:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
198 | scanf("%d", &par[i]);
| ~~~~~^~~~~~~~~~~~~~~
sending.cpp:208:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
208 | scanf("%d %d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 2 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 3 |
Correct |
19 ms |
25600 KB |
Output is correct |
| 4 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 5 |
Incorrect |
18 ms |
25600 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 2 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 3 |
Correct |
19 ms |
25600 KB |
Output is correct |
| 4 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 5 |
Incorrect |
18 ms |
25600 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 2 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 3 |
Correct |
19 ms |
25600 KB |
Output is correct |
| 4 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 5 |
Incorrect |
18 ms |
25600 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 2 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 3 |
Correct |
19 ms |
25600 KB |
Output is correct |
| 4 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 5 |
Incorrect |
18 ms |
25600 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
363 ms |
116592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
313 ms |
100720 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 2 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 3 |
Correct |
19 ms |
25600 KB |
Output is correct |
| 4 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 5 |
Incorrect |
18 ms |
25600 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 2 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 3 |
Correct |
19 ms |
25600 KB |
Output is correct |
| 4 |
Correct |
18 ms |
25600 KB |
Output is correct |
| 5 |
Incorrect |
18 ms |
25600 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
