Submission #852624

#	Time	Username	Problem	Language	Result	Execution time	Memory
852624		8pete8	꿈 (IOI13_dreaming)	C++17	100 / 100	56 ms	15736 KiB

dreaming

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
#include "dreaming.h"
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
const int mxn=1e5,mod=1000000007,lg=20,root=1000,inf=1e18;
int pa[mxn+10],mxdist[mxn+10],dist[mxn+10],mn[mxn+10];
vector<pii>adj[mxn+10];
vector<int>g[mxn+10];
bitset<mxn+10>yes,u;
int find(int u){return (u==pa[u])?u:pa[u]=find(pa[u]);}
void merg(int u,int v){
    int a=find(u),b=find(v);
    pa[a]=b;
}
void dfs(int cur,int p){
    for(auto i:adj[cur]){
        if(i.f==p)continue;
        dist[i.f]=dist[cur]+i.s;
        dfs(i.f,cur);
    }
}
void solve(int st){
    pii cur={st,0};
    while(cur.f!=-1){
        for(auto i:g[st])dist[i]=0;
        dfs(cur.f,-1);
        u[cur.f]=true;
        cur.f=-1;
        for(auto i:g[st]){
            if(mxdist[i]>=dist[i])continue;
            mxdist[i]=dist[i];
            if(cur.f==-1&&!u[i])cur={i,dist[i]};
            else if(dist[i]>cur.s&&!u[i])cur={i,dist[i]};
        }
    }
    for(auto i:g[st])mn[st]=min(mn[st],mxdist[i]);
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
    for(int i=0;i<N;i++)pa[i]=i;
    for(int i=0;i<M;i++){
        adj[A[i]].pb({B[i],T[i]});
        adj[B[i]].pb({A[i],T[i]});
        merg(A[i],B[i]);
    }
    for(int i=0;i<N;i++)g[find(i)].pb(i);
    vector<int>head;
    fill(mn,mn+N+1,INT_MAX);
    int ans=0;
    for(int i=0;i<N;i++){
        if(yes[pa[i]])continue;
        solve(pa[i]);
        yes[pa[i]]=true;
        head.pb(mn[pa[i]]);
    }
    for(int i=0;i<N;i++)ans=max(ans,mxdist[i]);
    sort(rall(head));
    if(head.size()>=1)ans=max(ans,head[0]);
    if(head.size()>=2)ans=max(ans,head[0]+head[1]+L);
    if(head.size()>=3)ans=max(ans,head[1]+head[2]+(2*L));
    return ans;
}
/*
int32_t main(){
    fastio
    int n,m;cin>>n>>m;
    int a[m],b[m],t[m];
    for(int i=0;i<m;i++)cin>>a[i]>>b[i]>>t[i];
    cout<<travelTime(n,m,2,a,b,t);
}*/

Compilation message (stderr)

dreaming.cpp:29:54: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   29 | const int mxn=1e5,mod=1000000007,lg=20,root=1000,inf=1e18;
      |                                                      ^~~~

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