IOI 2011 Day 1

https://oj.uz/problems/source/20

1. garden

첫 번째로, 각 정점마다 상태가 2가지가 있다.

1. 최솟값 간선으로 갈 수 있다. ( 이 간선을 전에 안 지남 )

2. 최솟값 간선으로 갈 수 없어서 두번째 최솟값 간선으로 간다. ( 최솟값 간선을 이미 지남 )

따라서 노드들의 상태를 위의 1, 2번 상태 2개로 나누어 만들자.

0~N-1 : 1번 노드 / N~2N-2 : 2번 노드

이제 각 노드들에서 다른 노드로 상태가 유일하게 정해지니, outdegree = 1인 그래프라고 생각할 수 있고, 이를 통해 Functional Graph 라는 것을 알 수 있다.

이제 마지막으로 원래 문제로 돌아가서 어떤 정점 P로부터 K번 간선을 지나고 얻을 수 있는 경로를 구해주면 된다. 일단 outdegree = 1을 간선들을 모두 뒤집어 indegree = 1로 만들고 P에서부터 dfs를 돌자.

functional graph의 특징상 중심에 사이클이 하나 있고 그 주변에 트리 여러개가 달린 모양이다. 이 꼴로 보아 P, P+N번 정점 2개에서 dfs를 돌면서 깊이가 x인 정점의 수들을 더해주면 되고, 사이클로 인한 주기성까지 생각하면 가장 간단한 방법이 O(NQ) 로 해결할 수 있다. 이때 주의할 정점은 도착해야 하는 정점은 모두 1번 종류여야 한다는 것이다.

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 3e5;
 
int N, M, P, Q;
int *G;
vector<int> adj2[MAXN+10];
vector<int> adj[MAXN+10];
 
int ans[MAXN+10];
int cnt[MAXN+10], cyc=-1;
int dep[MAXN+10];
 
void dfs(int now, int depth)
{
    //printf("%d\n", now);
    dep[now]=depth;
    for(auto nxt : adj[now])
    {
        if(dep[nxt]!=-1)
        {
            cyc=depth+1;
            continue;
        }
        dfs(nxt, depth+1);
    }
}
 
void count_routes(int _N, int _M, int _P, int R[][2], int _Q, int *_G)
{
    int i, j;
    N=_N; M=_M; P=_P; Q=_Q; G=_G;
 
    for(i=0; i<M; i++)
    {
        int u=R[i][0], v=R[i][1];
        adj2[u].push_back(v);
        adj2[v].push_back(u);
    }
 
    for(i=0; i<N; i++)
    {
        int nxt=adj2[i][0];
        if(adj2[nxt][0]==i) adj[nxt+N].push_back(i);//, printf("E%d %d\n", nxt+N, i);
        else adj[nxt].push_back(i);//, printf("E%d %d\n", nxt, i);
    }
 
    for(i=0; i<N; i++)
    {
        int nxt;
        if(adj2[i].size()==1) nxt=adj2[i][0];
        else nxt=adj2[i][1];
 
        if(adj2[nxt][0]==i) adj[nxt+N].push_back(i+N);//, printf("E%d %d\n", nxt+N, i+N);
        else adj[nxt].push_back(i+N);//, printf("E%d %d\n", nxt, i+N);
    }
 
    memset(cnt, 0, sizeof(cnt));
    memset(dep, -1, sizeof(dep));
    cyc=-1;
    dfs(P, 0);
    for(i=0; i<N; i++) cnt[dep[i]]++;
 
    for(i=0; i<Q; i++)
    {
        if(cyc==-1)
        {
            if(G[i]<2*N) ans[i]+=cnt[G[i]];
        }
        else
        {
            for(j=G[i]%cyc; j<2*N && j<=G[i]; j+=cyc) ans[i]+=cnt[j];
        }
    }
 
    //printf("!%d\n", cyc);
 
    memset(cnt, 0, sizeof(cnt));
    memset(dep, -1, sizeof(dep));
    cyc=-1;
    dfs(P+N, 0);
    for(i=0; i<N; i++) cnt[dep[i]]++;
 
    for(i=0; i<Q; i++)
    {
        if(cyc==-1)
        {
            if(G[i]<2*N) ans[i]+=cnt[G[i]];
        }
        else
        {
            for(j=G[i]%cyc; j<2*N && j<=G[i]; j+=cyc) ans[i]+=cnt[j];
        }
    }
 
    //printf("!%d\n", cyc);
    for(i=0; i<Q; i++) answer(ans[i]);
}

2. race

이 문제를 풀기 위해서 Centroid Decomposition을 사용한다.

거의 Centroid Decomposition의 기본 연습 문제와도 같은 간단한 문제이다.

어떤 Centroid 에서 거리가 x (x<=L) 인 정점까지의 최소 간선 수를 저장하는 배열을 만들고, 이 배열을 관리하면서 이 Centroid 가 해당되는 부분의 트리에 대해서 dfs를 돌면서 계산해주면 된다.

따라서 전체 시간 복잡도는 O(NlgN) 이다.

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 2e5;
const int MAXK = 1e6;
 
int N, K;
vector<pii> adj[MAXN+10];
 
bool del[MAXN+10];
int sz[MAXN+10], ans=987654321;
 
void getsz(int now, int bef)
{
    sz[now]=1;
    for(auto nxt : adj[now])
    {
        if(nxt.first==bef) continue;
        if(del[nxt.first]) continue;
        getsz(nxt.first, now);
        sz[now]+=sz[nxt.first];
    }
}
 
int getcen(int now, int bef, int tot)
{
    for(auto nxt : adj[now])
    {
        if(nxt.first==bef) continue;
        if(del[nxt.first]) continue;
        if(sz[nxt.first]>tot/2) return getcen(nxt.first, now, tot);
    }
    return now;
}
 
int M[MAXK+10];
vector<int> V;
 
void dfs1(int now, int bef, ll dist, int road)
{
    if(K-dist>=0) ans=min(ans, M[K-dist]+road);
    for(auto nxt : adj[now])
    {
        if(nxt.first==bef) continue;
        if(del[nxt.first]) continue;
        dfs1(nxt.first, now, dist+nxt.second, road+1);
    }
}
 
void dfs2(int now, int bef, ll dist, int road)
{
    if(dist<=K) M[dist]=min(M[dist], road), V.push_back(dist);
    for(auto nxt : adj[now])
    {
        if(nxt.first==bef) continue;
        if(del[nxt.first]) continue;
        dfs2(nxt.first, now, dist+nxt.second, road+1);
    }
}
 
void decomp(int now)
{
    getsz(now, now);
    now=getcen(now, now, sz[now]);
    del[now]=true;
 
    M[0]=0; V.clear();
    for(auto nxt : adj[now])
    {
        if(del[nxt.first]) continue;
        dfs1(nxt.first, nxt.first, nxt.second, 1);
        dfs2(nxt.first, nxt.first, nxt.second, 1);
    }
    for(auto it : V) M[it]=987654321;
 
    for(auto nxt : adj[now])
    {
        if(del[nxt.first]) continue;
        decomp(nxt.first);
    }
}
 
int best_path(int _N, int _K, int H[][2], int L[])
{
    int i, j;
    N=_N; K=_K;
    for(i=0; i<N-1; i++)
    {
        int u, v, w;
        u=H[i][0]+1; v=H[i][1]+1; w=L[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
 
    for(i=0; i<=K; i++) M[i]=987654321;
    decomp(1);
    if(ans==987654321) ans=-1;
    return ans;
}

3. ricehub

첫 번째로 어떠한 특정한 구간의 쌀들을 모두 한 곳으로 옮기기 위해서 어디에 쌀 창고를 설치해야 할까?

홀수이면 정확히 가운데, 짝수이면 가운데와 가운데+1의 아무 곳에 위치해도 된다.

이제 어떠한 구간을 잡았을 때 비용을 쉽게 구할 수 있고, 이 비용이 B를 넘지 않을 때 이 구간의 최대 길이를 구하는 것이 문제이다. 

구간 [l, r]보다는 구간 [l, r+1]의 비용이 더 크다는 것은 자명하다. 따라서 Two Pointer 을 이용한 Sliding Window 를 이용하여 최종 시간복잡도 O(N) 안에 쉽게 해결할 수 있다.

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
int R, L, *X, ans;
ll B;
 
int besthub(int _R, int _L, int *_X, ll _B)
{
    int i, j;
    R=_R; L=_L; X=_X; B=_B;
 
    ll S=0;
    for(i=0, j=0; i<R; i++)
    {
        while(S<=B && j<R) { j++; S+=X[j]-X[i+j>>1]; }
        S-=X[i+j+1>>1]-X[i];
        ans=max(ans, j-i);
    }
    return ans;
}