oj.uz

답안 #292853

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
292853 2020-09-07T14:14:13 Z 반딧불(#5810) 서류 전달 (ROI16_sending) C++17
0 / 100
 358 ms 116732 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 = 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(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:197:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  197 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sending.cpp:199:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  199 |         scanf("%d", &par[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
sending.cpp:209:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  209 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 25600 KB Output is correct
2 Correct 18 ms 25632 KB Output is correct
3 Correct 18 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 -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 25600 KB Output is correct
2 Correct 18 ms 25632 KB Output is correct
3 Correct 18 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 -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 25600 KB Output is correct
2 Correct 18 ms 25632 KB Output is correct
3 Correct 18 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 -

Subtask #4
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 25600 KB Output is correct
2 Correct 18 ms 25632 KB Output is correct
3 Correct 18 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 -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 358 ms 116732 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 308 ms 100720 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 25600 KB Output is correct
2 Correct 18 ms 25632 KB Output is correct
3 Correct 18 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 -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 25600 KB Output is correct
2 Correct 18 ms 25632 KB Output is correct
3 Correct 18 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 -