제출 #13128

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13128		gs14004	관광지 (IZhO14_shymbulak)	C++14	0 / 100	1500 ms	20704 KiB

shymbulak

#include <cstdio>
#include <vector>
#include <algorithm>
#include <deque>
#include <utility>
#include <queue>
using namespace std;
typedef pair<int,int> pi;

int n;
vector<int> graph[200005];

int low[200005], dfn[200005], piv;
int is_cyc[200005];

void dfs(int x, int pa){
    low[x] = dfn[x] = ++piv;
    for (int i=0; i<graph[x].size(); i++) {
        if(graph[x][i] == pa) continue;
        if(dfn[graph[x][i]]){
            is_cyc[graph[x][i]] = 1;
            low[x] = min(low[x],dfn[graph[x][i]]);
        }
        else{
            dfs(graph[x][i],x);
            low[x] = min(low[x],low[graph[x][i]]);
        }
    }
    if(low[x] < dfn[x]) is_cyc[x] = 1;
}

pi bfs(int x){
    queue<int> q,p,dist;
    q.push(x);
    p.push(0);
    dist.push(0);
    pi ret(0ll,0);
    while (!q.empty()) {
        int qf = q.front();
        int pf = p.front();
        int df = dist.front();
        q.pop();
        p.pop();
        dist.pop();
        ret = max(ret,pi(df,qf));
        for (int i=0; i<graph[qf].size(); i++) {
            int pos = graph[qf][i];
            if(is_cyc[pos] || pos == pf) continue;
            q.push(pos);
            p.push(qf);
            dist.push(df+1);
        }
    }
    return ret;
}

int nxt[200005], far[200005], bef[200005];

void solve(){
    int start_pos = 0, ret = 0, cnt = 0;
    for (int i=1; i<=n; i++) {
        if(is_cyc[i]) start_pos = i, cnt++;
    }
    int pos = start_pos, par = 0;
    int size = 0;
    do{
        is_cyc[pos] = 0;
        pi x = bfs(pos);
        far[pos] = x.first;
        ret = max(ret,bfs(x.second).first);
        is_cyc[pos] = 1;
        for (int i=0; i<graph[pos].size(); i++) {
            if(graph[pos][i] == par) continue;
            if(is_cyc[graph[pos][i]]){
                nxt[pos] = graph[pos][i];
                par = pos;
                pos = nxt[pos];
                bef[pos] = par;
                break;
            }
        }
        size++;
    }while (pos != start_pos);
    
    do{
        int pos2 = nxt[pos], i = 1;
        while (pos2 != pos) {
            ret = max(ret,far[pos] + far[pos2] + min(i,cnt-i));
            i++;
            pos2 = nxt[pos2];
        }
        pos = nxt[pos];
    }while (pos != start_pos);
    
    printf("%d",ret);
}

int main(){
    scanf("%d",&n);
    for (int i=0; i<n; i++) {
        int x,y;
        scanf("%d %d",&x,&y);
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    dfs(1,0);
    solve();
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50