oj.uz

Submission #402681

# Submission time Handle Problem Language Result Execution time Memory
402681 2021-05-12T08:47:12 Z victoriad Dreaming (IOI13_dreaming) C++14
0 / 100
 54 ms 9288 KB 
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>
#include <iomanip>
#include <fstream>
using namespace std;
#include "dreaming.h"

pair<int,int> menormayor(vector<int>&d1,vector<int>&d2,vector<int>&d3,vector<vector<pair<int,int> > >&g,int raiz){
    queue<int>cola;
    cola.push(raiz);
    int u=raiz,MAX=raiz;
    d1[u]=0;
    vector<int>cc;
    while(!cola.empty()){
        u=cola.front();
        cola.pop();
        cc.push_back(u);
        if(d1[u]>d1[MAX])MAX=u;
        for(pair<int,int>c:g[u]){
            if(d1[c.first]>d1[u]+c.second){
                d1[c.first]=d1[u]+c.second;
                cola.push(c.first);
            }
        }
    }
    cola.push(MAX);
    int MAX2=MAX;
    d2[MAX]=0;
    while(!cola.empty()){
        u=cola.front();
        cola.pop();
        if(d2[u]>d2[MAX2])MAX2=u;
        for(pair<int,int>c:g[u]){
            if(d2[c.first]>d2[u]+c.second){
                d2[c.first]=d2[u]+c.second;
                cola.push(c.first);
            }
        }
    }
    cola.push(MAX2);
    d3[MAX2]=0;
    while(!cola.empty()){
        u=cola.front();
        cola.pop();
        for(pair<int,int>c:g[u]){
            if(d3[c.first]>d3[u]+c.second){
                d3[c.first]=d3[u]+c.second;
                cola.push(c.first);
            }
        }
    }
    int e=1e9;
    for(int i=0;i<cc.size();i++){
        e=min(e,max(d2[cc[i]],d3[cc[i]]));
    }

    return make_pair(e,d2[MAX2]);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    vector<vector<pair<int,int> > >g(N);
    for(int i=0;i<M;i++){
        int a=A[i],b=B[i],c=T[i];
        g[a].push_back(make_pair(b,c));
        g[b].push_back(make_pair(a,c));
    }
    vector<int>d1(N,1e9);
    vector<int>d2(N,1e9);
    vector<int>d3(N,1e9);
    vector<int>ecc,dia;
    int CC=1;
    for(int i=0;i<N;i++){
        if(d1[i]==1e9){
            pair<int,int>e=menormayor(d1,d2,d3,g,i);
            ecc.push_back(e.first);
            dia.push_back(e.second);
            CC++;
        }
    }
    int r=0;
    for(int i=1;i<CC;i++){
        if(ecc[i]>ecc[0]){
            swap(ecc[i],ecc[0]);
        }
    }
    if(CC>1){
        for(int i=2;i<CC;i++){
            if(ecc[i]>ecc[1]){
            swap(ecc[i],ecc[1]);
            }
        }
        r=ecc[0]+ecc[1]+L;
    }
    if(CC>2){
        for(int i=3;i<CC;i++){
            if(ecc[i]>ecc[2])
            swap(ecc[i],ecc[2]);
        }
        r=max(r,ecc[1]+ecc[2]+2*L);
    }
    for(int i=0;i<CC;i++){
        r=max(r,dia[i]);
    }
    return r;
    
}

Compilation message

dreaming.cpp: In function 'std::pair<int, int> menormayor(std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<std::vector<std::pair<int, int> > >&, int)':
dreaming.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i=0;i<cc.size();i++){
      |                 ~^~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8644 KB Output is correct
2 Correct 51 ms 9288 KB Output is correct
3 Correct 33 ms 6236 KB Output is correct
4 Correct 8 ms 1684 KB Output is correct
5 Correct 7 ms 1228 KB Output is correct
6 Correct 13 ms 2388 KB Output is correct
7 Incorrect 1 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8644 KB Output is correct
2 Correct 51 ms 9288 KB Output is correct
3 Correct 33 ms 6236 KB Output is correct
4 Correct 8 ms 1684 KB Output is correct
5 Correct 7 ms 1228 KB Output is correct
6 Correct 13 ms 2388 KB Output is correct
7 Incorrect 1 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 6960 KB Output is correct
2 Correct 37 ms 6968 KB Output is correct
3 Correct 35 ms 6944 KB Output is correct
4 Correct 36 ms 7040 KB Output is correct
5 Correct 33 ms 6952 KB Output is correct
6 Correct 39 ms 7616 KB Output is correct
7 Correct 38 ms 7236 KB Output is correct
8 Correct 35 ms 6900 KB Output is correct
9 Correct 36 ms 6768 KB Output is correct
10 Correct 42 ms 7144 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 18 ms 4696 KB Output is correct
13 Correct 19 ms 4752 KB Output is correct
14 Correct 17 ms 4752 KB Output is correct
15 Correct 15 ms 4728 KB Output is correct
16 Correct 15 ms 4724 KB Output is correct
17 Correct 15 ms 4772 KB Output is correct
18 Correct 18 ms 4880 KB Output is correct
19 Correct 19 ms 4700 KB Output is correct
20 Incorrect 1 ms 204 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8644 KB Output is correct
2 Correct 51 ms 9288 KB Output is correct
3 Correct 33 ms 6236 KB Output is correct
4 Correct 8 ms 1684 KB Output is correct
5 Correct 7 ms 1228 KB Output is correct
6 Correct 13 ms 2388 KB Output is correct
7 Incorrect 1 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -