oj.uz

Submission #858013

# Submission time Handle Problem Language Result Execution time Memory
858013 2023-10-07T10:19:31 Z yusufhocaoglu Dreaming (IOI13_dreaming) C++17
0 / 100
 1000 ms 20608 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
#define int long long
#define pri pair<int,int>
using namespace std;
struct node {
    vector<pri> adj;
};

int32_t travelTime(int32_t N, int32_t M, int32_t L, int32_t A[], int32_t B[], int32_t T[]) {
    vector<node> nodes(N);
    for (int i = 0;i<M;i++) {
        nodes[A[i]].adj.push_back({B[i],T[i]});
        nodes[B[i]].adj.push_back({A[i],T[i]});
    }
    auto bfs = [nodes,N](int src) {
        queue<int> q;q.push(src);
        vector<int> trail(N,1e9);
        vector<int> dist(N,-1);
        trail[src]=-1;
        dist[src]=0;
        while (q.size()) {
            auto f = q.front();
            for (int i = 0;i<nodes[f].adj.size();i++) {
                if (nodes[f].adj[i].first==trail[f]) continue;
                trail[nodes[f].adj[i].first] = f;
                dist[nodes[f].adj[i].first] = dist[f] + nodes[f].adj[i].second;
                q.push(nodes[f].adj[i].first);
            }   
            q.pop();
        }
        return pair<vector<int>,vector<int>>{dist,trail};
    };
    vector<int> visit(N,0);
    vector<int> paths;
    for (int i = 0;i<N;i++) {
        if (visit[i]==1) continue;
        auto res = bfs(i);
        pri mxd = {-1,-1};
        for (int j = 0;j<N;j++) {
            if (res.second[j]!=1e9) visit[j]=1;
            if (res.first[j] > mxd.first) {
                mxd = {res.first[j],j};
            }
        }
        auto res2 = bfs(mxd.second);
        mxd = {-1,-1};
        for (int j = 0;j<N;j++) {
            if (res2.first[j] > mxd.first) {
                mxd = {res2.first[j],j};
            }
        }
        int tl = mxd.first;
        int t = res2.second[mxd.second];
        int mn = (t==-1)?0:1e9;
        while (t!=-1) {
            mn=min(mn,max(res2.first[t],tl-res2.first[t]));
            t = res2.second[t];
        }
        paths.push_back(mn);
    }
    sort(paths.begin(),paths.end());
    if (paths.size()==1) return paths[0];
    else if (paths.size()==2) return paths[1]+paths[0]+L;
    else return max(paths[paths.size()-1]+paths[paths.size()-2]+L,paths[paths.size()-2]+paths[paths.size()-3]+2*L);

    //return 12;
}

Compilation message

dreaming.cpp: In lambda function:
dreaming.cpp:24:29: 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]
   24 |             for (int i = 0;i<nodes[f].adj.size();i++) {
      |                            ~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1012 ms 15020 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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