제출 #120922

#제출 시각아이디문제언어결과실행 시간메모리
120922KieranHorgan마상시합 토너먼트 (IOI12_tournament)C++17
49 / 100
1045 ms14584 KiB
#include <bits/stdc++.h> using namespace std; vector<int> AdjList[200005]; int sz[200005]; int curNode = 1; int N, C, R, *K, *S, *E; int actualIdxToNode[100005]; int nodeToActualIdx[100005]; void addNode(int id, int curIdx, int idxToAdd, int sizeToAdd) { if(AdjList[id].empty()) { for(int i = 0; i < sizeToAdd; i++) { AdjList[id].push_back(++curNode); sz[curNode] = 1; } } else { for(auto v: AdjList[id]) { if(curIdx + sz[v] <= idxToAdd) { curIdx += sz[v]; } else { addNode(v, curIdx, idxToAdd, sizeToAdd); break; } } } sz[id] = 0; for(auto v: AdjList[id]) sz[id] += sz[v]; } int curActualIdx = 0; void assignIdx(int id) { if(sz[id] == 1) { actualIdxToNode[curActualIdx] = id; nodeToActualIdx[id] = curActualIdx++; return; } for(auto v: AdjList[id]) assignIdx(v); } int depth[200005]; int kthAncestor[200005][20]; void getDepth(int u, int d) { depth[u] = d; for(auto v: AdjList[u]) { kthAncestor[v][0] = u; getDepth(v, d-1); } } void calcKthAncestor() { kthAncestor[1][0] = 0; for(int i = 1+1; i <= curNode; i++) for(int j = 1; j < 20; j++) kthAncestor[i][j] = kthAncestor[kthAncestor[i][j-1]][j-1]; } int lca(int a, int b) { for(int j = 19; j >= 0; j--) if(depth[a] + (1<<j) <= depth[b]) a = kthAncestor[a][j]; for(int j = 19; j >= 0; j--) if(depth[b] + (1<<j) <= depth[a]) b = kthAncestor[b][j]; for(int j = 19; j >= 0; j--) if(kthAncestor[a][j] != kthAncestor[b][j]) { a = kthAncestor[a][j]; b = kthAncestor[b][j]; } if(a != b) { a = kthAncestor[a][0]; b = kthAncestor[b][0]; } return a; } int closestToLeft[100005]; int closestToRight[100005]; int GetBestPosition(int N_, int C_, int R_, int *K_, int *S_, int *E_) { N=N_, C=C_, R=R_; K=K_, S=S_, E=E_; sz[1] = 1; for(int i = C-1; i >= 0; i--) addNode(1, 0, S[i], E[i]-S[i]+1); assignIdx(1); getDepth(1,C); calcKthAncestor(); closestToLeft[0] = -1; for(int i = 1; i <= N; i++) { closestToLeft[i] = closestToLeft[i-1]; if(K[i-1] > R) closestToLeft[i] = i-1; } closestToRight[N-1] = -1; for(int i = N-1-1; i >= 0; i--) { closestToRight[i] = closestToRight[i+1]; if(K[i+1-1] > R) closestToRight[i] = i+1; } int ans = -1; int pos = -1; for(int i = 0; i < N; i++) { int a = 0; if(closestToLeft[i] == -1) { a = C-depth[actualIdxToNode[i]]; } else { a = depth[lca(actualIdxToNode[i], actualIdxToNode[closestToLeft[i]])]-depth[actualIdxToNode[i]]-1; } int b = 0; if(closestToRight[i] == -1) { b = C-depth[actualIdxToNode[i]]; } else { b = depth[lca(actualIdxToNode[i], actualIdxToNode[closestToRight[i]])]-depth[actualIdxToNode[i]]-1; } if(min(a,b) > ans) { ans = min(a,b); pos = i; } } return pos; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...