제출 #592902

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
592902		chirathnirodha	Dreaming (IOI13_dreaming)	C++17	18 / 100	73 ms	19672 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first 
#define S second 
#define P push
#define I insert
typedef long long ll;
const ll INF=1000000000000000;
const int maxn=100000;
ll n,m,l;
vector<pair<int,ll> > v[maxn];
vector<int> rts;
int parent[maxn];
ll maxsublen[maxn];
ll maxlen[maxn];
int gr[maxn];
ll dfs(int x,int z){
    for(int i=0;i<v[x].size();i++){
        int y=v[x][i].F;
        if(parent[x]==y)continue;
        parent[y]=x;
        gr[y]=z;
        maxsublen[x]=max(maxsublen[x],dfs(y,z)+v[x][i].S);
    }
    return maxsublen[x];
}
void dfs1(int x,ll maxpar){
    vector<pair<ll,int> > subs;
    for(int i=0;i<v[x].size();i++){
        int y=v[x][i].F;
        if(parent[x]==y)continue;
        subs.PB(MP(maxsublen[y]+v[x][i].S,y));
    }
    sort(subs.rbegin(),subs.rend());
    for(int i=0;i<v[x].size();i++){
        int y=v[x][i].F;
        if(parent[x]==y)continue;
        ll nmaxpar;
        if(subs.size()==1)nmaxpar=maxpar;
        else if(subs[0].S==y)nmaxpar=max(maxpar,subs[1].F);
        else nmaxpar=max(maxpar,subs[0].F);
        nmaxpar+=v[x][i].S;
        maxlen[y]=max(maxsublen[y],nmaxpar);
        dfs1(y,nmaxpar);
    }
    return;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n=N;m=M;l=(ll)L;
    for(int i=0;i<m;i++){
        v[A[i]].PB(MP(B[i],(ll)T[i]));
        v[B[i]].PB(MP(A[i],(ll)T[i]));
    }
    memset(parent,-1,sizeof(parent));
    memset(maxsublen,0,sizeof(maxsublen));
    for(int i=0;i<n;i++){
        if(parent[i]!=-1)continue;
        parent[i]=i;
        rts.PB(i);
        gr[i]=rts.size()-1;
        dfs(i,rts.size()-1);
        maxlen[i]=maxsublen[i];
        dfs1(i,0);
    }
    ll grmin[rts.size()];
    for(int i=0;i<rts.size();i++)grmin[i]=INF;
    for(int i=0;i<n;i++){
        grmin[gr[i]]=min(grmin[gr[i]],maxlen[i]);
    }
    sort(grmin,grmin+rts.size());
    reverse(grmin,grmin+rts.size());
    ll ans=INF;
    if(rts.size()==1)ans=grmin[0];
    else if(rts.size()==2)ans=grmin[0]+grmin[1]+l;
    else {
        ans=max(grmin[0]+grmin[1]+l,grmin[1]+grmin[2]+2*l);
    }
    return ans;
}

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

dreaming.cpp: In function 'll dfs(int, int)':
dreaming.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
dreaming.cpp: In function 'void dfs1(int, ll)':
dreaming.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
dreaming.cpp:38:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:69:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i=0;i<rts.size();i++)grmin[i]=INF;
      |                 ~^~~~~~~~~~~

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