Submission #531721

#	Time	Username	Problem	Language	Result	Execution time	Memory
531721		__Variatto	Dreaming (IOI13_dreaming)	C++17	100 / 100	115 ms	15760 KiB

dreaming

#include <bits/stdc++.h>
#include"dreaming.h"
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=1e5+10, MAXV=1e9+10;
int n, m, l, odl[MAX][2];
vector<pair<int,int>>g[MAX];
pair<int,int>maxi;
bool odw[MAX];
void dfso(int v, int oj, int x, int nr){
    odl[v][nr]=x;
    odw[v]=true;
    maxi=max(maxi, {x, v});
    for(auto s: g[v])
        if(s.fi!=oj)
            dfso(s.fi, v, x+s.se, nr);
}
pair<int,int>mini;
void dfs(int v, int oj){
    mini=min(mini, {max(odl[v][0], odl[v][1]), v});
    for(auto s: g[v])
        if(s.fi!=oj)
            dfs(s.fi,v);
}
int travelTime(int N, int M, int L, int a[], int b[], int t[]){
    n=N, m=M, l=L;
    for(int i=0; i<m; i++)
        g[a[i]].pb({b[i], t[i]}), g[b[i]].pb({a[i], t[i]});
    vector<int>v;
    int maxiSr=0;
    for(int i=0; i<n; i++){
        if(odw[i])
            continue;
        maxi={0,0};
        dfso(i, i, 0, 0);
        int s1=maxi.se;
        maxi={0,0};
        dfso(s1, s1, 0, 0);
        int s2=maxi.se;
        maxi={0,0};
        dfso(s2, s2, 0, 1);
        maxiSr=max(maxiSr, maxi.fi);
        mini={MAXV,0};
        dfs(i, i);
        int mid=mini.se;
        v.pb(max(odl[mid][0], odl[mid][1]));
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    if(v.size()>=2)
        maxiSr=max(maxiSr, v[0]+v[1]+l);
    if(v.size()>=3)
        maxiSr=max(maxiSr, v[1]+v[2]+2*l);
    return maxiSr;
}
/*int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int N, M, L;
    cin>>N>>M>>L;
    int A[M+2], B[M+2], T[M+2];
    for(int i=0; i<M; i++)
        cin>>A[i]>>B[i]>>T[i];
    cout<<travelTime(N, M, L, A, B, T)<<"\n";
 
}*/

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