제출 #172475

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
172475		Lukoloz	꿈 (IOI13_dreaming)	C++14	0 / 100	75 ms	11516 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define MAXN 100005
#define INF 999999999
using namespace std;
int ind,dpu[MAXN],dpd[MAXN],mx[MAXN][2],arr[MAXN],ans,ans1,per[MAXN];
int N,M,L,A[MAXN],B[MAXN],T[MAXN];
vector <pair<int,int> > g[MAXN];
bool fl[MAXN];
void dfs1(int i){
    fl[i]=1;
    for (int j=0; j<g[i].size(); j++){
        if (fl[g[i][j].ff]) continue;
        dfs1(g[i][j].ff);
        dpd[i]=max(dpd[i],dpd[g[i][j].ff]+g[i][j].ss);
    }
    fl[i]=0;
}
void dfs2(int i){
    fl[i]=1;
    arr[ind]=min(arr[ind],max(dpu[i],dpd[i]));

    // cout<<i<<" - "<<dpu[i]<<" "<<dpd[i]<<endl;

    for (int j=0; j<g[i].size(); j++){
        if (fl[g[i][j].ff]) continue;
        if (dpd[g[i][j].ff]+g[i][j].ss>mx[i][0]) mx[i][0]=dpd[g[i][j].ff]+g[i][j].ss;
        sort(mx[i],mx[i]+2);
    }

    // cout<<mx[0]<<" - "<<mx[1]<<endl;

    for (int j=0; j<g[i].size(); j++){
        if (fl[g[i][j].ff]) continue;
        if (dpd[g[i][j].ff]+g[i][j].ss==mx[i][1]) dpu[g[i][j].ff]=max(dpu[i],mx[i][0])+g[i][j].ss;
        else dpu[g[i][j].ff]=max(dpu[i],mx[i][1])+g[i][j].ss;  
    }

    ans1=max(ans1,max(mx[i][0],dpu[i])+mx[i][1]);
    
    for (int j=0; j<g[i].size(); j++){
        if (fl[g[i][j].ff]) continue;
        dfs2(g[i][j].ff); 
    }
}
int travelTime(int n,int m,int l,int a[],int b[],int t[]){
    for (int i=0; i<m; i++){
        g[a[i]].pb({b[i],t[i]});
        g[b[i]].pb({a[i],t[i]});
    }
    
    for(int i=0; i<n; i++){
        if (fl[i]) continue;
        arr[ind]=INF;
        dfs1(i); 
        dfs2(i);
        // cout<<"------------ arr - "<<arr[ind]<<" "<<i<<endl;
        // cout<<mx[i][1]+mx[i][0]<<endl;
        ind++;
    }
    // cout<<ans1<<endl;

    sort(arr,arr+ind);

    ans=max(arr[ind-3]+arr[ind-2]+2*l,arr[ind-1]+arr[ind-2]+l);

    return max(ans,ans1);
}
// int main() {
    // cin>>N>>M>>L;
    // for (int i=0; i<M; i++) cin>>A[i]>>B[i]>>T[i];
    // cout<<travelTime(N,M,L,A,B,T)<<endl;
// }
/*
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

*/

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

dreaming.cpp: In function 'void dfs1(int)':
dreaming.cpp:16:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j=0; j<g[i].size(); j++){
                   ~^~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int)':
dreaming.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j=0; j<g[i].size(); j++){
                   ~^~~~~~~~~~~~
dreaming.cpp:37:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j=0; j<g[i].size(); j++){
                   ~^~~~~~~~~~~~
dreaming.cpp:45:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j=0; j<g[i].size(); j++){
                   ~^~~~~~~~~~~~

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