Submission #592890

#	Time	Username	Problem	Language	Result	Execution time	Memory
592890		chirathnirodha	Dreaming (IOI13_dreaming)	C++17	0 / 100	52 ms	20940 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;
int 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[0].S==y && subs.size()>1)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=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());
    ll ans=INF;
    if(rts.size()==1)ans=grmin[0];
    else if(rts.size()==2)ans=grmin[0]+grmin[1]+l;
    else {
        ans=min(grmin[0]+grmin[1]+l,grmin[1]+grmin[2]+2*l);
    }
    return ans;
}

Compilation message (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:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     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: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23