Submission #172458

#	Time	Username	Problem	Language	Result	Execution time	Memory
172458		Lukoloz	Dreaming (IOI13_dreaming)	C++14	0 / 100	1068 ms	9720 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[2],arr[MAXN],ans,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;
    mx[0]=mx[1]=0;
    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[0]) mx[0]=dpd[g[i][j].ff]+g[i][j].ss;
        sort(mx,mx+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[1]) dpu[g[i][j].ff]=max(dpu[i],mx[0])+g[i][j].ss;
        else dpu[g[i][j].ff]=max(dpu[i],mx[1])+g[i][j].ss;  
    }
    
    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;
 
        ind++;
    }
 
    sort(arr,arr+ind);
 
    for (int i=0; i<(ind+1)/2; i++){
        per[ind-1-i]=arr[i*2+1];    
        per[i]=arr[i*2];
    }
 
    for (int ln=1; ln<ind; ln++){
        for (int j=0; j<ind-ln; j++)
            ans=max(ans,l*ln+per[j]+per[j+ln]);
    }
 
    return ans;
}
// 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
 
*/

Compilation message (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:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j=0; j<g[i].size(); j++){
                   ~^~~~~~~~~~~~
dreaming.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j=0; j<g[i].size(); j++){
                   ~^~~~~~~~~~~~
dreaming.cpp:44: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