제출 #760675

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
760675		bgnbvnbv	Dreaming (IOI13_dreaming)	C++14	100 / 100	84 ms	28020 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll lab[maxN];
ll findset(ll x)
{
    return lab[x]<0?x:lab[x]=findset(lab[x]);
}
void unite(ll u,ll v)
{
    u=findset(u);
    v=findset(v);
    if(u==v) return;
    if(lab[u]>lab[v]) swap(u,v);
    lab[u]+=lab[v];
    lab[v]=u;
}
vector<pli>g[maxN];
ll n,m;
vector<ll>vec[maxN];
ll h[maxN][3];
void dfs(ll u,ll p,ll t)
{
    for(auto zz:g[u])
    {
        if(zz.fi!=p)
        {
            h[zz.fi][t]=h[u][t]+zz.se;
            dfs(zz.fi,u,t);
        }
    }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    n=N,m=M;
    for(int i=0;i<N;i++) lab[i]=-1;
    for(int i=0;i<M;i++)
    {
        unite(A[i],B[i]);
        g[A[i]].pb({B[i],T[i]});
        g[B[i]].pb({A[i],T[i]});
    }
    for(int i=0;i<n;i++)
    {
        vec[findset(i)].pb(i);
    }
    ll ans=0;
    vector<pli>cc;
    for(int i=0;i<n;i++)
    {
        if(findset(i)==i)
        {
            dfs(i,i,0);
            ll mx=-1,id=0;
            for(auto u:vec[i])
            {
                if(h[u][0]>mx)
                {
                    mx=h[u][0];
                    id=u;
                }
            }
            dfs(id,id,1);
            mx=-1,id=0;
            for(auto u:vec[i])
            {
                if(h[u][1]>mx)
                {
                    mx=h[u][1];
                    id=u;
                }
            }
            ans=max(ans,mx);
            dfs(id,id,2);
            mx=inf,id=0;
            for(auto u:vec[i])
            {
                if(max(h[u][1],h[u][2])<mx)
                {
                    mx=max(h[u][1],h[u][2]);
                    id=u;
                }
            }
            cc.pb({mx,id});
        }
    }
    sort(cc.begin(),cc.end(),greater<pli>());
    ll dm=inf;
    for(int i=0;i<cc.size();i++)
    {
        ll mx1=-inf,mx2=-inf;
        for(int j=0;j<cc.size();j++)
        {
            if(j==i) continue;
            if(mx1==-inf)
            {
                mx1=cc[j].fi;
            }
            else if(mx2==-inf) mx2=cc[j].fi;
            if(mx2!=-inf) break;
        }
        dm=min(dm,max(mx1+mx2+2*L,cc[i].fi+mx1+L));
    }
    ans=max(ans,dm);
    return ans;
}
/*void solve()
{
    cout << travelTime(12,8,2,{0, 8, 2, 5, 5, 1, 1, 10},{8, 2, 7, 11, 1, 3, 9, 6},{4, 2, 4, 3, 7, 1, 5, 3});
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}*/

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

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:99:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for(int i=0;i<cc.size();i++)
      |                 ~^~~~~~~~~~
dreaming.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for(int j=0;j<cc.size();j++)
      |                     ~^~~~~~~~~~

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