Submission #1022695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022695		boyliguanhan	Jousting tournament (IOI12_tournament)	C++17	100 / 100	232 ms	37892 KiB

tournament

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>OST;
set<int>st;
int N,dep[200100],bj[200100][20],ACT[100100];
vector<int>adj[200100];
void dfs(int n){
    dep[n]=dep[bj[n][0]]+1;
    for(int i=1;i<20;i++)
        bj[n][i]=bj[bj[n][i-1]][i-1];
    for(auto i:adj[n])
        bj[i][0]=n,dfs(i);
}
int lca(int a,int b){
    if(!b||b>N)return 0;
    if(dep[a]<dep[b])swap(a,b);
    for(int i=20;i--;)
        if(dep[bj[a][i]]>=dep[b])
            a=bj[a][i];
    for(int i=20;i--;)
        if(bj[a][i]-bj[b][i])
            a=bj[a][i],b=bj[b][i];
    return dep[bj[a][0]];
}
void initn(int n){N=n;}
pair<int,int>ans;
void dotheproc(int a,int b){
    for(int i=a+1;i<b;i++)
        ans=max(ans,{dep[i]-max(lca(i,a),lca(i,b)),-i});
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    initn(N);
    for(int i=1;i<=N;i++)
        OST.insert(i),ACT[i]=i,st.insert(i);
    for(int q=1;q<=C;q++){
        auto it=OST.find_by_order(S[q-1]);
        auto it2=OST.find_by_order(E[q-1]+1);
        vector<int>v;
        while(it!=it2)
            v.push_back(*it++);
        for(auto i:v) OST.erase(i),
            adj[N+q].push_back(ACT[i]),st.erase(i);
        ACT[v[0]]=N+q;
        OST.insert(v[0]);
        st.insert(v[0]);
    }
    dfs(N+C);
    vector<int>G{0};
    for(int i=1;i<N;i++)
        if(K[i-1]>R)G.push_back(i);
    G.push_back(N);
    for(int i=1;i<G.size();i++) 
        dotheproc(G[i-1],G[i]+1);
    return -ans.second-1;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i=1;i<G.size();i++)
      |                 ~^~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51