제출 #65515

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
65515		XmtosX	Race (IOI11_race)	C++17	0 / 100	25 ms	23928 KiB

race

#include <bits/stdc++.h>
#include "race.h"
//#include "graderlib.c"

using namespace std;

const int MAXN=2e5+5;
int n,sz[MAXN],lvl[MAXN],mx,st,sprs[MAXN][20],par[MAXN];
int sum[MAXN][20];
int ans=1e9;
pair<int,int> c[MAXN];
bool yes,vis[MAXN];
vector <pair<int,int> > v[MAXN];
vector <int> here[MAXN];
vector <pair<int,pair<int,int> > > cen[MAXN];
set<pair<int,pair<int,int> > > s[MAXN];
set<pair<int,pair<int,int> > > :: iterator it;
void init (int x,int p,int w)
{
    sz[x]=1;
    lvl[x]=lvl[p]+1;
    if (yes)
    {
        sprs[x][0]=p;
        sum[x][0]=w;
        for (int i=1;i<20;i++)
        {
            sprs[x][i]=sprs[sprs[x][i-1]][i-1];
            sum[x][i]=sum[x][i-1]+(sum[sprs[x][i-1]][i-1]);
        }
    }
    for (int i=0;i<v[x].size();i++)
    {
        int nxt=v[x][i].first;
        if (nxt!=p)
        {
            init(nxt,x,v[x][i].second);
            sz[x]+=sz[nxt];
        }
    }
}
pair<int,int> lca (int x,int y)
{
    if (lvl[x]<lvl[y])
        swap(x,y);
    if (y==n)
        return make_pair(0,0);
    int a=0,b=0;
    for (int i=19;i>=0;i--)
    {
        if (lvl[sprs[x][i]]>=lvl[y])
        {
            a+= (sum[x][i]);
            x=sprs[x][i];
            b+=(1<<i);
        }
    }
    if (x==y)
    {
        return make_pair(a,b);
    }
    for (int i=19;i>=0;i--)
    {
        if (sprs[x][i]!=sprs[y][i])
        {
            a+= (sum[x][i]+sum[y][i]);
            x=sprs[x][i];
            y=sprs[y][i];
            b+= (1<<i)*2;
        }
    }
    b+=2;
    a+= (sum[x][0]+sum[y][0]);
    return make_pair(a,b);
}

void dfs (int x,int p,int N,int P,int X)
{
    int maxx=0;
    if (N==1)
    {
        cen[x].push_back({P,lca(P,x)});
        cen[P].push_back({x,lca(P,x)});
        vis[x]=true;
        return ;
    }
    for (int i=0;i<v[x].size();i++)
    {
        int nxt=v[x][i].first;
        if (lvl[nxt]>lvl[x]&&!vis[nxt])
        {
            maxx=max(maxx,sz[nxt]);
        }
        else if (lvl[nxt]>=lvl[X]&&!vis[nxt])
        {
            maxx=max(maxx,sz[X]-sz[x]);
        }
    }
    if (maxx<=N/2)
    {
        vis[x]=true;
        cen[P].push_back({x,lca(P,x)});
        cen[x].push_back({P,lca(P,x)});
        for (int i=0;i<v[x].size();i++)
        {
            int nxt=v[x][i].first;
            if (lvl[nxt]>lvl[x]&&!vis[nxt])
            {
                dfs(nxt,x,sz[nxt],x,nxt);
            }
            else if (lvl[X]<=lvl[nxt]&&!vis[nxt])
            {
                dfs(nxt,x,sz[X]-sz[x],x,X);
            }
        }
        return;
    }
    for (int i=0;i<v[x].size();i++)
    {
        int nxt=v[x][i].first;
        if (nxt!=p&&!vis[nxt])
        {
            dfs(nxt,x,N,P,X);
        }
    }
}
void init1(int x,int p,pair<int,int> pp)
{
    par[x]=p;
    lvl[x]=lvl[p]+1;
    c[x]= pp;
    here[lvl[x]].push_back(x);
    for (int i=0;i<cen[x].size();i++)
    {
        int nxt= (cen[x][i].first);
        if (nxt!=p)
            init1(nxt,x,cen[x][i].second);
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    n=N;
    for (int i=0;i<=n;i++)
    {
        for (int j=0;j<20;j++)
            sprs[i][j]=n;
    }
    for (int i=0;i<n-1;i++)
    {
        v[H[i][1]].push_back({H[i][0],L[i]});
        v[H[i][0]].push_back({H[i][1],L[i]});
    }
    init(0,n,0);
    for (int i=0;i<n;i++)
    {
        int maxx=0;
        for (int j=0;j<v[i].size();j++)
        {
            int nxt=v[i][j].first;
            if (lvl[nxt]>lvl[i])
            {
                maxx=max(maxx,sz[nxt]);
            }
            else
            {
                maxx=max(maxx,sz[0]-sz[i]);
            }
        }
        if (maxx<=n/2)
        {
            st=i;
            break;
        }
    }
    yes=true;
    init(st,n,0);
    dfs(st,-1,n,n,st);
    init1(st,n,make_pair(0,0));
    for (int i=0;i<n;i++)
    {
        s[i].insert({1e9,{1e9,1e9}});
        s[i].insert({0,{0,N}});
    }
    for (int i=30;i>0;i--)
    {
        for (int j=0;j<here[i].size();j++)
        {
            int x=here[i][j];
            int k=0;
            int cnt=0;
            if (x==n)
                continue;
            //cout <<x<<" ";
            while (par[x]!=n)
            {
                cnt+= c[x].second;
                k+= c[x].first;
                pair<int,pair<int,int> > p;
                if (k>K)
                    break;
                p.first=k;
                p.second= {cnt,x};
                it= s[par[x]].lower_bound(p);
                if ((*it).first==k&&(*it).second.second==x)
                {
                    if ((*it).second.first<cnt)
                        break;
                    s[par[x]].erase(it);
                }
                s[par[x]].insert(p);
                x=par[x];
            }
        }
        //cout <<endl;
    }
    for (int i=0;i<n;i++)
    {
        int k=0;
        int cnt=0;
        int x=i;
        while (par[x]!=n)
        {
            cnt+= c[x].second;
            k+= c[x].first;
            pair<int,pair<int,int> > p;
            if (k>K)
                break;
            p.first=K-k;
            p.second= {0,0};
            it= s[par[x]].lower_bound(p);
            if ((*it).first==p.first)
            {
                if ((*it).second.second==x)
                    it++;
                if ((*it).first==p.first)
                    ans=min(ans,cnt+(*it).second.first);
            }
            x=par[x];
        }
    }
    if (ans==1e9)
        ans=-1;
    return ans;
}
/*
int main()
{
    return _main(best_path);
}
*/

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'void init(int, int, int)':
race.cpp:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();i++)
                  ~^~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int, int, int)':
race.cpp:87:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();i++)
                  ~^~~~~~~~~~~~
race.cpp:104:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<v[x].size();i++)
                      ~^~~~~~~~~~~~
race.cpp:118:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();i++)
                  ~^~~~~~~~~~~~
race.cpp: In function 'void init1(int, int, std::pair<int, int>)':
race.cpp:133:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<cen[x].size();i++)
                  ~^~~~~~~~~~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:157:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0;j<v[i].size();j++)
                      ~^~~~~~~~~~~~
race.cpp:186:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0;j<here[i].size();j++)
                      ~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57