oj.uz

Submission #592902

# Submission time Handle Problem Language Result Execution time Memory
592902 2022-07-09T19:15:12 Z chirathnirodha Dreaming (IOI13_dreaming) C++17
18 / 100
 73 ms 19672 KB 
#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;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 19672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 19672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8016 KB Output is correct
2 Correct 24 ms 8124 KB Output is correct
3 Correct 26 ms 8056 KB Output is correct
4 Correct 25 ms 8140 KB Output is correct
5 Correct 32 ms 8008 KB Output is correct
6 Correct 28 ms 8320 KB Output is correct
7 Correct 27 ms 8264 KB Output is correct
8 Correct 20 ms 8036 KB Output is correct
9 Correct 20 ms 8016 KB Output is correct
10 Correct 22 ms 8272 KB Output is correct
11 Correct 2 ms 3796 KB Output is correct
12 Correct 5 ms 6220 KB Output is correct
13 Correct 6 ms 6348 KB Output is correct
14 Correct 7 ms 6220 KB Output is correct
15 Correct 6 ms 6220 KB Output is correct
16 Correct 6 ms 6220 KB Output is correct
17 Correct 6 ms 6320 KB Output is correct
18 Correct 7 ms 6348 KB Output is correct
19 Correct 6 ms 6220 KB Output is correct
20 Correct 2 ms 3796 KB Output is correct
21 Correct 2 ms 3796 KB Output is correct
22 Correct 2 ms 3924 KB Output is correct
23 Correct 7 ms 6220 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 19672 KB Output isn't correct
2 Halted 0 ms 0 KB -