Submission #388776

#	Time	Username	Problem	Language	Result	Execution time	Memory
388776		anonymous	ROI16_sending (ROI16_sending)	C++14	0 / 100	480 ms	344224 KiB

sending

#include <iostream>
#include <utility>
#include <map>
#include <algorithm>
#include <vector>
#define MAXN 200005
#define fi first
#define se second
using namespace std;
int N, K, P[MAXN], Route[MAXN][2], Ans, pt = 1;
int Preorder[MAXN], Pos[MAXN][2], depth[MAXN], anc[MAXN][19];
vector <pair<int,int> > Path[MAXN];
vector <int> adj[MAXN], Back[MAXN];
//precalc

void preorder(int u) {
    Preorder[pt] = u;
    Pos[u][0] = pt;
    depth[u] = depth[P[u]] + 1;
    pt++;
    for (int v: adj[u]) {
        preorder(v);
    }
    Pos[u][1] = pt-1;
}

void makejump() {
    for (int i=1; i <= N; i++) {
        anc[i][0] = P[i];
    }
    for (int j=1; j<= 18; j++) {
        for (int i=1; i <= N; i++) {
            anc[i][j] = anc[anc[i][j-1]][j-1];
        }
    }
}

int lca(int a, int b) {
    if (depth[a] > depth[b]) {swap(a,b);}
    for (int i=18; i>=0; i--) {
        if ((depth[b] - depth[a]) & (1<<i)) {b = anc[b][i];}
    }
    for (int i=18; i>=0; i--) {
        if (anc[a][i] != anc[b][i]) {
            a = anc[a][i];
            b = anc[b][i];
        }
    }
    if (a != b) {return(anc[a][0]);}
    return(a);
}

int D(int a, int b) { //distance
    return(depth[a] + depth[b] - 2*depth[lca(a,b)]);
}

void precalc() {
    for (int i=2; i<=N; i++) {
        adj[P[i]].push_back(i);
    }
    preorder(1);
    makejump();
    for (int i=1; i<=K; i++) {
        int v = lca(Route[i][0], Route[i][1]);
        Back[Route[i][0]].push_back(v);
        Back[Route[i][1]].push_back(v);
        if (Route[i][0] == v || Route[i][1] == v) {continue;}
        Path[v].push_back({Route[i][0], Route[i][1]});
    }
}
//classes

class CompressedTree {
     int Par[MAXN * 10], big[MAXN * 10], Val[MAXN * 10], len[MAXN * 10], dist[MAXN * 10], V=1;
     map<int,int> M[MAXN * 10];
     vector <int> Tadj[MAXN * 10];
public:
     int addnode(int val, int d) { //root go to 0
        Val[V] = val, len[V] = d;
        big[V] = V;
        V+=1;
        return(V-1); //return label assigned to
     }

     void setpar(int chdId, int parId) {
        Par[chdId] = parId;
     }

     void reset() { //probs can zero other stuff too
          for (int i=1; i<V; i++) {
            M[i].clear();
            Tadj[i].clear();
          }
          V = 1;
     }
     void build() {
         for (int i=V-1; i>1; i--) {
            Tadj[Par[i]].push_back(i);
         }
         for (int i=2; i<V; i++) {
            dist[i] = dist[Par[i]] + len[i];
         }
     }
     int slv(int u, int rt) {
         M[u][Pos[Val[u]][0]] = Val[u]; //actual node id of the other one
         for (int v: Tadj[u]) {
            int res = slv(v, rt);
            if (M[res].size() > M[big[u]].size()) {
                swap(res, big[u]);
            }
            for (auto p: M[res]) {
                auto it = M[big[u]].upper_bound(p.fi);
                if (it != M[big[u]].end()) {
                    Ans = max(Ans, dist[u] + depth[lca(p.se, (*it).se)] - depth[rt]);
                }
                if (it != M[big[u]].begin()) {
                    Ans = max(Ans, dist[u] + depth[lca(p.se, (*(--it)).se)] - depth[rt]);
                }
                M[big[u]][p.fi] = p.se;
            }
         }
         return(big[u]);
     }
} CT;

//solve stuff
int dfs1(int u) { //case where paths don't share lca
    int bh = 1 << 30, sbh = 1 << 30;
    for (int v: Back[u]) {
        if (depth[v] < bh) {
            sbh = bh;
            bh = depth[v];
        } else if (depth[v] < sbh) {
            sbh = depth[v];
        }
    }
    for (int v: adj[u]) {
        int res = dfs1(v);
        if (res < bh) {
            sbh = bh;
            bh = res;
        } else if (res < sbh) {
            sbh = res;
        }
    }
    Ans = max(Ans, depth[u] - sbh);
    return(bh);
}

void slvLCA(int v) { //slv all path with common lca V
    if (Path[v].size() < 2) {return;}
    vector <pair<int,int> > Nodes, Nodes2; //fi Nodes is ET, fi Nodes2 is depth
    map <int,int> Sweep; //Euler tour, compressed tree Id

    for (auto p: Path[v]) {
        Nodes.push_back({Pos[p.first][0], p.first});
        Nodes.push_back({Pos[p.second][0], p.second});
    }
    sort(Nodes.begin(), Nodes.end()); //sort by ET
    for (int i=0; i<Nodes.size()-1; i++) {
        int junction = lca(Nodes[i].second, Nodes[i+1].second);
        Nodes2.push_back({depth[junction], junction});
        Nodes2.push_back({depth[Nodes[i].second], Nodes[i].second});
        Nodes2.push_back({depth[Nodes[i+1].second], Nodes[i+1].second});
    }
    for (int i=Nodes2.size()-1; i>=0; i--) {
        if (i+1 < Nodes2.size() && Nodes2[i] == Nodes[i+1]) {continue;} //remove duplicates
        int v = Nodes2[i].second;
        int vid = CT.addnode(v, depth[v]);
        auto it = Sweep.lower_bound(Pos[v][0]);
        for (; it != Sweep.end(); it=Sweep.erase(it)) {
            if ((*it).first <= Pos[v][1]) {
                CT.setpar((*it).second, vid);
            }
        }
    }
    CT.build();
    CT.slv(1, v);
    CT.reset();
}

int main() {
    //freopen("courin.txt","r",stdin);
    scanf("%d %d",&N,&K);
    for (int i=2; i<=N; i++) {
        scanf("%d",&P[i]);
    }
    for (int i=1; i<=K; i++) {
        scanf("%d %d",&Route[i][0], &Route[i][1]);
    }
    precalc();
    dfs1(1);
    for (int i=1; i<=N; i++) {
        slvLCA(i);
    }
    printf("%d", Ans);
}

Compilation message (stderr)

sending.cpp: In function 'void slvLCA(int)':
sending.cpp:160:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |     for (int i=0; i<Nodes.size()-1; i++) {
      |                   ~^~~~~~~~~~~~~~~
sending.cpp:167:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |         if (i+1 < Nodes2.size() && Nodes2[i] == Nodes[i+1]) {continue;} //remove duplicates
      |             ~~~~^~~~~~~~~~~~~~~
sending.cpp: In function 'int main()':
sending.cpp:184:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  184 |     scanf("%d %d",&N,&K);
      |     ~~~~~^~~~~~~~~~~~~~~
sending.cpp:186:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  186 |         scanf("%d",&P[i]);
      |         ~~~~~^~~~~~~~~~~~
sending.cpp:189:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  189 |         scanf("%d %d",&Route[i][0], &Route[i][1]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 29
• Subtask 2: 0 / 12
• Subtask 3: 0 / 7
• Subtask 4: 0 / 8
• Subtask 5: 0 / 10
• Subtask 6: 0 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 10