oj.uz

Submission #291454

# Submission time Handle Problem Language Result Execution time Memory
291454 2020-09-05T10:45:44 Z cig32 Dreaming (IOI13_dreaming) C++14
0 / 100
 251 ms 26008 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<pair<ll,ll> >adjlist[100000];
bool visited[100000];
pair<ll,ll> maxi={0,LLONG_MAX};
void dfs(ll node,ll dist_so_far){
    if(visited[node]==false){
        visited[node]=true;
        if(maxi.first<dist_so_far || (maxi.first==dist_so_far && maxi.second>node)){
            maxi={dist_so_far,node};
        }
        for(ll i=0;i<adjlist[node].size();i++){
            if(visited[adjlist[node][i].first]==false){
                dfs(adjlist[node][i].first,adjlist[node][i].second+dist_so_far);
            }
        }
    }
}
vector<ll>yes;
stack<ll>hmph;
void dfs2(ll node,ll dist_so_far){
    if(visited[node]==false){
        visited[node]=true;
        hmph.push(node);
        if(maxi.first==dist_so_far && maxi.second==node){
            while(hmph.size()){
                yes.push_back(hmph.top());
                hmph.pop();
            }
            reverse(yes.begin(),yes.end());
            return;
        }
        for(ll i=0;i<adjlist[node].size();i++){
            if(visited[adjlist[node][i].first]==false){
                dfs2(adjlist[node][i].first,adjlist[node][i].second+dist_so_far);
            }
        }
        if(hmph.size()) hmph.pop();
    }
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
    map<pair<ll,ll>,ll>mp;
    for(ll i=0;i<M;i++){
        adjlist[A[i]].push_back({B[i],T[i]});
        adjlist[B[i]].push_back({A[i],T[i]});
        mp[{A[i],B[i]}]=T[i];
        mp[{B[i],A[i]}]=T[i];
    }
    for(ll i=0;i<N;i++) visited[i]=false;
    vector<ll>starting;
    for(ll i=0;i<N;i++){
        if(visited[i]==false){
            dfs(i,0);
            starting.push_back(maxi.second);
            maxi={0,LLONG_MAX};
        }
    }
    for(ll i=0;i<N;i++){
        visited[i]=false;
    }
    vector<pair<ll,ll> > diameters;
    vector<vector<ll> > paths;
    vector<pair<ll,ll> > maxrecord;
    for(ll i=0;i<starting.size();i++){
        dfs(starting[i],0);
        diameters.push_back({starting[i],maxi.second});
        maxrecord.push_back(maxi);
        maxi={0,LLONG_MAX};
    }
    for(ll i=0;i<N;i++){
        visited[i]=false;
    }
    for(ll i=0;i<starting.size();i++){
        maxi=maxrecord[i];
        dfs2(starting[i],0);
        paths.push_back(yes);
        yes.clear();
    }
    ll ans=0;
    vector<ll>segments;
    for(ll i=0;i<paths.size();i++){
        ans=max(ans,maxrecord[i].first);
        ll good=LLONG_MAX;
        ll sofar=0;
        for(ll j=0;j<paths[i].size();j++){
            if(max(maxrecord[i].first-sofar,sofar)<good){
                good=max(maxrecord[i].first-sofar,sofar);
                sofar+=mp[{paths[i][j],paths[i][j+1]}];
            }
            else break;
        }
        segments.push_back(good);
    }
    ll d=segments.size();
    sort(segments.begin(),segments.end());
    ans=max(ans,segments[d-1]+segments[d-2]+L);
    ans=max(ans,segments[d-2]+segments[d-3]+2*L);
    return ans;
}

Compilation message

dreaming.cpp: In function 'void dfs(long long int, long long int)':
dreaming.cpp:14:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |         for(ll i=0;i<adjlist[node].size();i++){
      |                    ~^~~~~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(long long int, long long int)':
dreaming.cpp:35:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for(ll i=0;i<adjlist[node].size();i++){
      |                    ~^~~~~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:66:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(ll i=0;i<starting.size();i++){
      |                ~^~~~~~~~~~~~~~~~
dreaming.cpp:75:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(ll i=0;i<starting.size();i++){
      |                ~^~~~~~~~~~~~~~~~
dreaming.cpp:83:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(ll i=0;i<paths.size();i++){
      |                ~^~~~~~~~~~~~~
dreaming.cpp:87:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(ll j=0;j<paths[i].size();j++){
      |                    ~^~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 26008 KB Output is correct
2 Correct 238 ms 25992 KB Output is correct
3 Correct 135 ms 18004 KB Output is correct
4 Correct 21 ms 6144 KB Output is correct
5 Correct 17 ms 4992 KB Output is correct
6 Correct 39 ms 7928 KB Output is correct
7 Incorrect 2 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 26008 KB Output is correct
2 Correct 238 ms 25992 KB Output is correct
3 Correct 135 ms 18004 KB Output is correct
4 Correct 21 ms 6144 KB Output is correct
5 Correct 17 ms 4992 KB Output is correct
6 Correct 39 ms 7928 KB Output is correct
7 Incorrect 2 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 26008 KB Output is correct
2 Correct 238 ms 25992 KB Output is correct
3 Correct 135 ms 18004 KB Output is correct
4 Correct 21 ms 6144 KB Output is correct
5 Correct 17 ms 4992 KB Output is correct
6 Correct 39 ms 7928 KB Output is correct
7 Incorrect 2 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 17256 KB Output is correct
2 Correct 121 ms 17772 KB Output is correct
3 Correct 113 ms 17768 KB Output is correct
4 Correct 113 ms 17768 KB Output is correct
5 Correct 116 ms 17640 KB Output is correct
6 Correct 128 ms 19076 KB Output is correct
7 Correct 119 ms 18412 KB Output is correct
8 Correct 116 ms 17640 KB Output is correct
9 Correct 109 ms 17384 KB Output is correct
10 Correct 120 ms 18280 KB Output is correct
11 Correct 3 ms 2816 KB Output is correct
12 Correct 42 ms 19200 KB Output is correct
13 Correct 44 ms 19212 KB Output is correct
14 Correct 43 ms 19208 KB Output is correct
15 Correct 44 ms 19392 KB Output is correct
16 Correct 42 ms 19212 KB Output is correct
17 Correct 44 ms 19212 KB Output is correct
18 Correct 43 ms 19216 KB Output is correct
19 Correct 43 ms 19216 KB Output is correct
20 Incorrect 2 ms 2688 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 26008 KB Output is correct
2 Correct 238 ms 25992 KB Output is correct
3 Correct 135 ms 18004 KB Output is correct
4 Correct 21 ms 6144 KB Output is correct
5 Correct 17 ms 4992 KB Output is correct
6 Correct 39 ms 7928 KB Output is correct
7 Incorrect 2 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 26008 KB Output is correct
2 Correct 238 ms 25992 KB Output is correct
3 Correct 135 ms 18004 KB Output is correct
4 Correct 21 ms 6144 KB Output is correct
5 Correct 17 ms 4992 KB Output is correct
6 Correct 39 ms 7928 KB Output is correct
7 Incorrect 2 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -