| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1018217 | NintsiChkhaidze | Jousting tournament (IOI12_tournament) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pb push_back
#include "tournament.h"
#define pii pair <int,int>
#define f first
#define s second
#define left h*2,l,(l+r)/2
#define right h*2+1,(l+r)/2+1,r
using namespace std;
const int M = 10000+5;
vector <int> g[M];
int dp[M],par[M];
void dfs(int x,int par){
for (int to: g[x]){
dfs(to,x);
dp[x]=max(dp[x],dp[to]);
}
}
int GetBestPosition(int N, int C, int R, int K[], int S[], int E[]){
int n = N;
int id = 1;
vector <int> leaves;
leaves.pb(id);
for (int i = C - 1; i >= 0; i--){
int l = S[i],r = E[i],cnt = 0;
vector <int> nw;
for (int j=0;j<l;j++){
nw.pb(leaves[j]);
}
for (int j = l; j <= r; j++){
nw.pb(++id);
par[id] = leaves[l];
g[leaves[l]].pb(id);
}
for (int j = l + 1; j < leaves.size(); j++)
nw.pb(leaves[j]);
leaves = nw;
}
int ans=-1,pos=-1;
for (int i=0;i<n;i++){
vector <int> v;
int l = 0;
for (int j = 0; j < N; j++){
if (i == j) v.pb(R);
else v.pb(K[l++]);
}
for (int j = 1; j <= id; j++)
dp[j] = 0;
int x = 0;
for (int j = 0; j < n; j++){
dp[leaves[j]] = v[j];
if (v[j] == R){
x = leaves[j];
}
}
dfs(1,1);
int cur = 0;
x = par[x];
while (x && dp[x] == R){
++cur;
x = par[x];
}
if (cur > ans){
ans = cur;
pos = i;
}
}
return pos;
}