oj.uz

Submission #291456

# Submission time Handle Problem Language Result Execution time Memory
291456 2020-09-05T10:47:49 Z cig32 Dreaming (IOI13_dreaming) C++14
0 / 100
 237 ms 26136 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[]){
    if(N==1){
        return 0;
    }
    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:69: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]
   69 |     for(ll i=0;i<starting.size();i++){
      |                ~^~~~~~~~~~~~~~~~
dreaming.cpp:78: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]
   78 |     for(ll i=0;i<starting.size();i++){
      |                ~^~~~~~~~~~~~~~~~
dreaming.cpp:86: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]
   86 |     for(ll i=0;i<paths.size();i++){
      |                ~^~~~~~~~~~~~~
dreaming.cpp:90: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]
   90 |         for(ll j=0;j<paths[i].size();j++){
      |                    ~^~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 26136 KB Output is correct
2 Correct 237 ms 25992 KB Output is correct
3 Correct 133 ms 18004 KB Output is correct
4 Correct 23 ms 6144 KB Output is correct
5 Correct 17 ms 4992 KB Output is correct
6 Correct 37 ms 7928 KB Output is correct
7 Incorrect 3 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 228 ms 26136 KB Output is correct
2 Correct 237 ms 25992 KB Output is correct
3 Correct 133 ms 18004 KB Output is correct
4 Correct 23 ms 6144 KB Output is correct
5 Correct 17 ms 4992 KB Output is correct
6 Correct 37 ms 7928 KB Output is correct
7 Incorrect 3 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 228 ms 26136 KB Output is correct
2 Correct 237 ms 25992 KB Output is correct
3 Correct 133 ms 18004 KB Output is correct
4 Correct 23 ms 6144 KB Output is correct
5 Correct 17 ms 4992 KB Output is correct
6 Correct 37 ms 7928 KB Output is correct
7 Incorrect 3 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 111 ms 17260 KB Output is correct
2 Correct 130 ms 17516 KB Output is correct
3 Correct 116 ms 17256 KB Output is correct
4 Correct 114 ms 17476 KB Output is correct
5 Correct 117 ms 17276 KB Output is correct
6 Correct 127 ms 18688 KB Output is correct
7 Correct 118 ms 18028 KB Output is correct
8 Correct 109 ms 17004 KB Output is correct
9 Correct 110 ms 16996 KB Output is correct
10 Correct 121 ms 17952 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 42 ms 19216 KB Output is correct
13 Correct 43 ms 19336 KB Output is correct
14 Correct 46 ms 19208 KB Output is correct
15 Correct 43 ms 19212 KB Output is correct
16 Correct 43 ms 19204 KB Output is correct
17 Correct 44 ms 19208 KB Output is correct
18 Correct 44 ms 19204 KB Output is correct
19 Correct 43 ms 19216 KB Output is correct
20 Correct 2 ms 2688 KB Output is correct
21 Incorrect 2 ms 2688 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 26136 KB Output is correct
2 Correct 237 ms 25992 KB Output is correct
3 Correct 133 ms 18004 KB Output is correct
4 Correct 23 ms 6144 KB Output is correct
5 Correct 17 ms 4992 KB Output is correct
6 Correct 37 ms 7928 KB Output is correct
7 Incorrect 3 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 228 ms 26136 KB Output is correct
2 Correct 237 ms 25992 KB Output is correct
3 Correct 133 ms 18004 KB Output is correct
4 Correct 23 ms 6144 KB Output is correct
5 Correct 17 ms 4992 KB Output is correct
6 Correct 37 ms 7928 KB Output is correct
7 Incorrect 3 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -