제출 #306650

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
306650		talant117408	꿈 (IOI13_dreaming)	C++17	100 / 100	178 ms	18824 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;

#define pb push_back
#define mp make_pair

const int N = 1e5+7, INF = 0x3f3f3f3f;

int comp, tmpfurthdis, tmpfurth;
vector <int> compnum(N), compfurthdis(N, INF), compfurth(N), vis(N), disfromeach(N);
vector <pii> compends(N);
vector <vector <pii>> graph(N);
vector <vector <int>> compelem(N);

void findcomp(int v, int num){
    vis[v] = 1;
    compnum[v] = num;
    compelem[num].pb(v);
    for(auto to : graph[v]){
        if(!vis[to.first]){
            findcomp(to.first, num);
        }
    }
}

void findends(int v, int p = -1, int dis = 0){
    if(dis > tmpfurthdis){
        tmpfurthdis = dis;
        tmpfurth = v;
    }
    for(auto to : graph[v]){
        if(to.first != p){
            findends(to.first, v, dis+to.second);
        }
    }
}

void finddis(int v, int p = -1, int dis = 0){
    disfromeach[v] = max(disfromeach[v], dis);
    for(auto to : graph[v]){
        if(to.first != p){
            finddis(to.first, v, dis+to.second);
        }
    }
}

int travelTime(int n, int m, int l, int x[], int y[], int t[]) {
    int i, ans = 0;
    for(i = 0; i < m; i++){
        graph[x[i]].pb(mp(y[i], t[i]));
        graph[y[i]].pb(mp(x[i], t[i]));
    }
    
    for(i = 0; i < n; i++){
        if(!vis[i]){
            findcomp(i, comp++);
        }
    }
    
    for(i = 0; i < n; i++)
        vis[i] = 0;
        
    for(i = 0; i < comp; i++){
        int to = compelem[i][0];
        tmpfurthdis = 0;
        tmpfurth = to;
        findends(to);
        compends[i].first = tmpfurth;
        
        tmpfurthdis = 0;
        findends(tmpfurth);
        compends[i].second = tmpfurth;
        ans = max(ans, tmpfurthdis);
    }
    
    for(i = 0; i < comp; i++){
        finddis(compends[i].first);
        finddis(compends[i].second);
    }
    
    for(i = 0; i < n; i++){
        if(compfurthdis[compnum[i]] > disfromeach[i]){
            compfurthdis[compnum[i]] = disfromeach[i];
            compfurth[compnum[i]] = i;
        }
    }
    
    vector <int> dists;
    
    for(i = 0; i < comp; i++){
        dists.pb(compfurthdis[i]);
    }
    sort(dists.rbegin(), dists.rend());
    if(comp > 1){
        ans = max(ans, dists[0]+l+dists[1]);
    }
    if(comp > 2){
        ans = max(ans, dists[1]+l+l+dists[2]);
    }
    /*
    for(i = 0; i < n; i++){
        cout << compnum[i] << ' ';
    }
    cout << endl;
    for(i = 0; i < comp; i++){
        cout << compends[i].first << ' ' << compends[i].second << endl;
    }*/
    
    return ans;
}



/*
12 8 2
0 8 4
8 2 2 
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
*/


/*
int main(){
    int n, m, i, l;
    cin >> n >> m >> l;
    int x[m], y[m], t[m];
    for(i = 0; i < m; i++){
        cin >> x[i] >> y[i] >> t[i];
    }
    cout << travelTime(n, m, l, x, y, t);
}*/

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23