oj.uz

Submission #293058

# Submission time Handle Problem Language Result Execution time Memory
293058 2020-09-07T15:52:32 Z 반딧불(#5810) ROI16_sending (ROI16_sending) C++17
41 / 100
 5000 ms 52724 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]);
}

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));
    }

    for(int i=1; i<=n; i++){
        findAnswer(i, st);
        memset(centroidUsed, 0, sizeof(centroidUsed));
    }
    printf("%d\n%d %d", ans, ansX, ansY);
}

Compilation message

sending.cpp: In function 'int main()':
sending.cpp:200:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  200 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sending.cpp:203:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  203 |         scanf("%d", &par[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
sending.cpp:213:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  213 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
29.0 / 29.0

# 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 18 ms 25728 KB Output is correct
4 Correct 18 ms 25600 KB Output is correct
5 Correct 18 ms 25600 KB Output is correct
6 Correct 23 ms 25600 KB Output is correct
7 Correct 22 ms 25600 KB Output is correct
8 Correct 22 ms 25600 KB Output is correct
9 Correct 22 ms 25600 KB Output is correct
10 Correct 21 ms 25600 KB Output is correct
11 Correct 20 ms 25728 KB Output is correct
12 Correct 22 ms 25600 KB Output is correct
13 Correct 21 ms 25600 KB Output is correct
14 Correct 22 ms 25600 KB Output is correct
15 Correct 23 ms 25728 KB Output is correct
16 Correct 20 ms 25600 KB Output is correct
17 Correct 21 ms 25600 KB Output is correct
18 Correct 22 ms 25592 KB Output is correct
19 Correct 21 ms 25600 KB Output is correct

Subtask #2
12.0 / 12.0

# 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 18 ms 25728 KB Output is correct
4 Correct 18 ms 25600 KB Output is correct
5 Correct 18 ms 25600 KB Output is correct
6 Correct 23 ms 25600 KB Output is correct
7 Correct 22 ms 25600 KB Output is correct
8 Correct 22 ms 25600 KB Output is correct
9 Correct 22 ms 25600 KB Output is correct
10 Correct 21 ms 25600 KB Output is correct
11 Correct 20 ms 25728 KB Output is correct
12 Correct 22 ms 25600 KB Output is correct
13 Correct 21 ms 25600 KB Output is correct
14 Correct 22 ms 25600 KB Output is correct
15 Correct 23 ms 25728 KB Output is correct
16 Correct 20 ms 25600 KB Output is correct
17 Correct 21 ms 25600 KB Output is correct
18 Correct 22 ms 25592 KB Output is correct
19 Correct 21 ms 25600 KB Output is correct
20 Correct 2563 ms 26724 KB Output is correct
21 Correct 2629 ms 26848 KB Output is correct
22 Correct 3179 ms 27180 KB Output is correct
23 Correct 3334 ms 27268 KB Output is correct
24 Correct 2616 ms 27068 KB Output is correct
25 Correct 1966 ms 26880 KB Output is correct
26 Correct 3219 ms 27568 KB Output is correct
27 Correct 1965 ms 26688 KB Output is correct
28 Correct 2122 ms 26732 KB Output is correct
29 Correct 2605 ms 27296 KB Output is correct
30 Correct 3000 ms 27364 KB Output is correct
31 Correct 2608 ms 27184 KB Output is correct
32 Correct 3350 ms 27384 KB Output is correct
33 Correct 2348 ms 27276 KB Output is correct

Subtask #3
0 / 7.0

# 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 18 ms 25728 KB Output is correct
4 Correct 18 ms 25600 KB Output is correct
5 Correct 18 ms 25600 KB Output is correct
6 Correct 23 ms 25600 KB Output is correct
7 Correct 22 ms 25600 KB Output is correct
8 Correct 22 ms 25600 KB Output is correct
9 Correct 22 ms 25600 KB Output is correct
10 Correct 21 ms 25600 KB Output is correct
11 Correct 20 ms 25728 KB Output is correct
12 Correct 22 ms 25600 KB Output is correct
13 Correct 21 ms 25600 KB Output is correct
14 Correct 22 ms 25600 KB Output is correct
15 Correct 23 ms 25728 KB Output is correct
16 Correct 20 ms 25600 KB Output is correct
17 Correct 21 ms 25600 KB Output is correct
18 Correct 22 ms 25592 KB Output is correct
19 Correct 21 ms 25600 KB Output is correct
20 Correct 2563 ms 26724 KB Output is correct
21 Correct 2629 ms 26848 KB Output is correct
22 Correct 3179 ms 27180 KB Output is correct
23 Correct 3334 ms 27268 KB Output is correct
24 Correct 2616 ms 27068 KB Output is correct
25 Correct 1966 ms 26880 KB Output is correct
26 Correct 3219 ms 27568 KB Output is correct
27 Correct 1965 ms 26688 KB Output is correct
28 Correct 2122 ms 26732 KB Output is correct
29 Correct 2605 ms 27296 KB Output is correct
30 Correct 3000 ms 27364 KB Output is correct
31 Correct 2608 ms 27184 KB Output is correct
32 Correct 3350 ms 27384 KB Output is correct
33 Correct 2348 ms 27276 KB Output is correct
34 Execution timed out 5065 ms 49016 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# 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 18 ms 25728 KB Output is correct
4 Correct 18 ms 25600 KB Output is correct
5 Correct 18 ms 25600 KB Output is correct
6 Correct 23 ms 25600 KB Output is correct
7 Correct 22 ms 25600 KB Output is correct
8 Correct 22 ms 25600 KB Output is correct
9 Correct 22 ms 25600 KB Output is correct
10 Correct 21 ms 25600 KB Output is correct
11 Correct 20 ms 25728 KB Output is correct
12 Correct 22 ms 25600 KB Output is correct
13 Correct 21 ms 25600 KB Output is correct
14 Correct 22 ms 25600 KB Output is correct
15 Correct 23 ms 25728 KB Output is correct
16 Correct 20 ms 25600 KB Output is correct
17 Correct 21 ms 25600 KB Output is correct
18 Correct 22 ms 25592 KB Output is correct
19 Correct 21 ms 25600 KB Output is correct
20 Correct 2563 ms 26724 KB Output is correct
21 Correct 2629 ms 26848 KB Output is correct
22 Correct 3179 ms 27180 KB Output is correct
23 Correct 3334 ms 27268 KB Output is correct
24 Correct 2616 ms 27068 KB Output is correct
25 Correct 1966 ms 26880 KB Output is correct
26 Correct 3219 ms 27568 KB Output is correct
27 Correct 1965 ms 26688 KB Output is correct
28 Correct 2122 ms 26732 KB Output is correct
29 Correct 2605 ms 27296 KB Output is correct
30 Correct 3000 ms 27364 KB Output is correct
31 Correct 2608 ms 27184 KB Output is correct
32 Correct 3350 ms 27384 KB Output is correct
33 Correct 2348 ms 27276 KB Output is correct
34 Execution timed out 5065 ms 49016 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5078 ms 52724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5049 ms 51368 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# 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 18 ms 25728 KB Output is correct
4 Correct 18 ms 25600 KB Output is correct
5 Correct 18 ms 25600 KB Output is correct
6 Correct 23 ms 25600 KB Output is correct
7 Correct 22 ms 25600 KB Output is correct
8 Correct 22 ms 25600 KB Output is correct
9 Correct 22 ms 25600 KB Output is correct
10 Correct 21 ms 25600 KB Output is correct
11 Correct 20 ms 25728 KB Output is correct
12 Correct 22 ms 25600 KB Output is correct
13 Correct 21 ms 25600 KB Output is correct
14 Correct 22 ms 25600 KB Output is correct
15 Correct 23 ms 25728 KB Output is correct
16 Correct 20 ms 25600 KB Output is correct
17 Correct 21 ms 25600 KB Output is correct
18 Correct 22 ms 25592 KB Output is correct
19 Correct 21 ms 25600 KB Output is correct
20 Correct 2563 ms 26724 KB Output is correct
21 Correct 2629 ms 26848 KB Output is correct
22 Correct 3179 ms 27180 KB Output is correct
23 Correct 3334 ms 27268 KB Output is correct
24 Correct 2616 ms 27068 KB Output is correct
25 Correct 1966 ms 26880 KB Output is correct
26 Correct 3219 ms 27568 KB Output is correct
27 Correct 1965 ms 26688 KB Output is correct
28 Correct 2122 ms 26732 KB Output is correct
29 Correct 2605 ms 27296 KB Output is correct
30 Correct 3000 ms 27364 KB Output is correct
31 Correct 2608 ms 27184 KB Output is correct
32 Correct 3350 ms 27384 KB Output is correct
33 Correct 2348 ms 27276 KB Output is correct
34 Execution timed out 5065 ms 49016 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 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 18 ms 25728 KB Output is correct
4 Correct 18 ms 25600 KB Output is correct
5 Correct 18 ms 25600 KB Output is correct
6 Correct 23 ms 25600 KB Output is correct
7 Correct 22 ms 25600 KB Output is correct
8 Correct 22 ms 25600 KB Output is correct
9 Correct 22 ms 25600 KB Output is correct
10 Correct 21 ms 25600 KB Output is correct
11 Correct 20 ms 25728 KB Output is correct
12 Correct 22 ms 25600 KB Output is correct
13 Correct 21 ms 25600 KB Output is correct
14 Correct 22 ms 25600 KB Output is correct
15 Correct 23 ms 25728 KB Output is correct
16 Correct 20 ms 25600 KB Output is correct
17 Correct 21 ms 25600 KB Output is correct
18 Correct 22 ms 25592 KB Output is correct
19 Correct 21 ms 25600 KB Output is correct
20 Correct 2563 ms 26724 KB Output is correct
21 Correct 2629 ms 26848 KB Output is correct
22 Correct 3179 ms 27180 KB Output is correct
23 Correct 3334 ms 27268 KB Output is correct
24 Correct 2616 ms 27068 KB Output is correct
25 Correct 1966 ms 26880 KB Output is correct
26 Correct 3219 ms 27568 KB Output is correct
27 Correct 1965 ms 26688 KB Output is correct
28 Correct 2122 ms 26732 KB Output is correct
29 Correct 2605 ms 27296 KB Output is correct
30 Correct 3000 ms 27364 KB Output is correct
31 Correct 2608 ms 27184 KB Output is correct
32 Correct 3350 ms 27384 KB Output is correct
33 Correct 2348 ms 27276 KB Output is correct
34 Execution timed out 5065 ms 49016 KB Time limit exceeded
35 Halted 0 ms 0 KB -