oj.uz

Submission #291435

# Submission time Handle Problem Language Result Execution time Memory
291435 2020-09-05T10:35:37 Z cig32 Dreaming (IOI13_dreaming) C++14
0 / 100
 220 ms 24684 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());
        }
        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);
            }
        }
        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:34: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]
   34 |         for(ll i=0;i<adjlist[node].size();i++){
      |                    ~^~~~~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:65: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]
   65 |     for(ll i=0;i<starting.size();i++){
      |                ~^~~~~~~~~~~~~~~~
dreaming.cpp:74: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]
   74 |     for(ll i=0;i<starting.size();i++){
      |                ~^~~~~~~~~~~~~~~~
dreaming.cpp:82: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]
   82 |     for(ll i=0;i<paths.size();i++){
      |                ~^~~~~~~~~~~~~
dreaming.cpp:86: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]
   86 |         for(ll j=0;j<paths[i].size();j++){
      |                    ~^~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 22392 KB Output is correct
2 Correct 220 ms 22392 KB Output is correct
3 Correct 114 ms 15608 KB Output is correct
4 Correct 19 ms 5504 KB Output is correct
5 Correct 16 ms 4864 KB Output is correct
6 Correct 34 ms 7160 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 209 ms 22392 KB Output is correct
2 Correct 220 ms 22392 KB Output is correct
3 Correct 114 ms 15608 KB Output is correct
4 Correct 19 ms 5504 KB Output is correct
5 Correct 16 ms 4864 KB Output is correct
6 Correct 34 ms 7160 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 209 ms 22392 KB Output is correct
2 Correct 220 ms 22392 KB Output is correct
3 Correct 114 ms 15608 KB Output is correct
4 Correct 19 ms 5504 KB Output is correct
5 Correct 16 ms 4864 KB Output is correct
6 Correct 34 ms 7160 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 Runtime error 77 ms 24684 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 22392 KB Output is correct
2 Correct 220 ms 22392 KB Output is correct
3 Correct 114 ms 15608 KB Output is correct
4 Correct 19 ms 5504 KB Output is correct
5 Correct 16 ms 4864 KB Output is correct
6 Correct 34 ms 7160 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 209 ms 22392 KB Output is correct
2 Correct 220 ms 22392 KB Output is correct
3 Correct 114 ms 15608 KB Output is correct
4 Correct 19 ms 5504 KB Output is correct
5 Correct 16 ms 4864 KB Output is correct
6 Correct 34 ms 7160 KB Output is correct
7 Incorrect 2 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -