oj.uz

Submission #292811

# Submission time Handle Problem Language Result Execution time Memory
292811 2020-09-07T13:42:28 Z 반딧불(#5810) ROI16_sending (ROI16_sending) C++17
0 / 100
 158 ms 37868 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[200002];

void dfsGroup(int x, int groupNum, int par = 0){
    group[x] = groupNum;
    in[x] = ++inCnt, inIdx[in[x]] = x;
    for(auto &y: link[x]){
        if(centroidUsed[y] || y==par) continue;
        depth[y] = depth[x]+1;
        dfsGroup(y, groupNum, x);
    }
}

void findAnswer(int c, vector<Path> &ust){
    vector<int> nearChild;
    vector<vector<pi> > groupVec;
    vector<vector<Path> > propVec;
    map<pi, vector<int> > groupMp;
    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);

    for(int i=0; i<s; i++){
        inCnt = 0;
        dfsGroup(nearChild[i], i);
    }
    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);
            groupMp[make_pair(tmp1, tmp2)].push_back(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


    /// propagate to childs
    for(auto &chd: centroidChild[c]){
        findAnswer(chd, propVec[group[chd]]);
    }
}

int main(){
    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:138:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  138 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sending.cpp:140:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  140 |         scanf("%d", &par[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
sending.cpp:150:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  150 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9984 KB Output is correct
2 Correct 8 ms 9984 KB Output is correct
3 Correct 7 ms 9984 KB Output is correct
4 Incorrect 7 ms 9984 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9984 KB Output is correct
2 Correct 8 ms 9984 KB Output is correct
3 Correct 7 ms 9984 KB Output is correct
4 Incorrect 7 ms 9984 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9984 KB Output is correct
2 Correct 8 ms 9984 KB Output is correct
3 Correct 7 ms 9984 KB Output is correct
4 Incorrect 7 ms 9984 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9984 KB Output is correct
2 Correct 8 ms 9984 KB Output is correct
3 Correct 7 ms 9984 KB Output is correct
4 Incorrect 7 ms 9984 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 101 ms 37868 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 158 ms 37612 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9984 KB Output is correct
2 Correct 8 ms 9984 KB Output is correct
3 Correct 7 ms 9984 KB Output is correct
4 Incorrect 7 ms 9984 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9984 KB Output is correct
2 Correct 8 ms 9984 KB Output is correct
3 Correct 7 ms 9984 KB Output is correct
4 Incorrect 7 ms 9984 KB Output isn't correct
5 Halted 0 ms 0 KB -