Submission #725380

#	Time	Username	Problem	Language	Result	Execution time	Memory
725380		yeyso	Dreaming (IOI13_dreaming)	C++14	47 / 100	1079 ms	19036 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    int n = N; int m = M; int l = L;
    vector<vector<int>> adj(n, vector<int>());
    vector<vector<int>> dma(n, vector<int>());

    vector<int> a(A, A+m);
    vector<int> b(B, B+m);
    vector<int> t(T, T+m);
    for(int i = 0; i < a.size(); i ++){
        adj[a[i]].push_back(b[i]); adj[b[i]].push_back(a[i]);
        dma[a[i]].push_back(t[i]); dma[b[i]].push_back(t[i]);
    }

    vector<int> components = {0};
    queue<int> q0; q0.push(0);
    vector<int> v(n, 0);
    int node = 0;
    while(!q0.empty()){
        node = q0.front();
        q0.pop();
        if(!v[node]){
            v[node] = 1;
            for(int i = 0; i < adj[node].size(); i ++){
                q0.push(adj[node][i]);
            }
        }
        if(q0.empty()){
            for(int i = 0; i < v.size(); i ++){
                if(v[i] == 0){
                    components.push_back(i);
                    q0.push(i);
                    break;
                }
            }
        }
    }
    queue<int> q;
    vector<int> d0(n, INT_MAX / 2); vector<int> v0(n, 0);
    vector<int> d(n, INT_MAX / 2); vector<int> visited(n, 0);
    vector<pair<int, int>> prefix0; vector<pair<int, int>> prefix;
    vector<vector<int>> prefixes;
    vector<int> maxsizes;
    vector<int> csize;
    vector<int> parents(n, -1); vector<int> parents0(n, -1);
    vector<int> centers;
    for(int x = 0; x < components.size(); x ++){
        prefix = prefix0;
        int furtherest = 0; int dist = 0;
        d = d0; visited = v0;
        parents = parents0;
        d[components[x]] = 0;
        // Finds the furtherest node in the component
        q.push(components[x]);
        while(!q.empty()){
            node = q.front();
            q.pop();
            if(!visited[node]){
                visited[node] = 1;
                for(int i = 0; i < adj[node].size(); i ++){
                    q.push(adj[node][i]);
                    d[adj[node][i]] = min(d[adj[node][i]], d[node] + dma[node][i]);
                    
                }
            }
        }

        for(int i = 0; i < visited.size(); i ++){
            if(visited[i]){
                if(d[i] >= dist){
                    dist = d[i];
                    furtherest = i;
                }
            }
        }
        // Generate a prefix array of nodes from the furtherest
        d = d0; visited = v0;
        d[furtherest] = 0;
        q.push(furtherest);
        while(!q.empty()){
            node = q.front();
            q.pop();
            if(!visited[node]){
                visited[node] = 1;
                for(int i = 0; i < adj[node].size(); i ++){
                    q.push(adj[node][i]);
                    //cout << d[node] << " ";
                    d[adj[node][i]] = min(d[adj[node][i]], d[node] + dma[node][i]);

                    if(!visited[adj[node][i]]){
                        parents[adj[node][i]] = node;
                    }
                }
            }
        }
        furtherest = 0;
        dist = 0;
        for(int i = 0; i < visited.size(); i ++){
            if(visited[i]){
                if(d[i] >= dist){
                    dist = d[i];
                    furtherest = i;
                }
            }
        }
        node = furtherest;
        dist = 0;
        while(node > -1){
            prefix.push_back({d[node], node});
            node = parents[node];
        }
        reverse(prefix.begin(), prefix.end());
        int maxd = prefix[prefix.size() - 1].first;
        int score = INT_MAX / 2;
        int best = INT_MAX / 2;
        int best_node = 0;
        for(int i = 0; i < prefix.size(); i ++){
            if(max(prefix[i].first, maxd - prefix[i].first) < best){
                best = max(prefix[i].first, maxd - prefix[i].first);
                best_node = prefix[i].second;
            }
        }
        centers.push_back(best_node);
        maxsizes.push_back(maxd);
        csize.push_back(best);
    }
    int largest_diameter = 0;
    int largest_component_center = 0;
    for(int i = 0; i < maxsizes.size(); i ++){
        if(maxsizes[i] > largest_diameter){
            largest_diameter = maxsizes[i];
            largest_component_center = centers[i];
        }
    }

    for(int i = 0; i < centers.size(); i ++){
        //cout << centers[i] << " ";
        if(centers[i] != largest_component_center){
            adj[centers[i]].push_back(largest_component_center);
            adj[largest_component_center].push_back(centers[i]);

            dma[centers[i]].push_back(l);
            dma[largest_component_center].push_back(l);
        }
    }
    //cout << "_ " << largest_component_center << " ";
    q.push(0);
    v = v0; d = d0;
    d[0] = 0;
    while(!q.empty()){
        node = q.front();
        q.pop();
        if(!v[node]){
            v[node] = 1;
            for(int i = 0; i < adj[node].size(); i ++){
                q.push(adj[node][i]);
                d[adj[node][i]] = min(d[adj[node][i]], d[node] + dma[node][i]);
            }
        }
    }
    int dist = 0;
    int furtherest = 0;
    for(int i = 0; i < d.size(); i ++){
        if(d[i] > dist){
            dist = d[i];
            furtherest = i;
        }
        //cout << v[i] << " ";
    }
    q.push(furtherest);
    v = v0; d = d0;
    d[furtherest] = 0;
    while(!q.empty()){
        node = q.front();
        q.pop();
        if(!v[node]){
            v[node] = 1;
            for(int i = 0; i < adj[node].size(); i ++){
                q.push(adj[node][i]);
                d[adj[node][i]] = min(d[adj[node][i]], d[node] + dma[node][i]);
            }
        }
    }
    dist = 0;
    furtherest = 0;
    for(int i = 0; i < d.size(); i ++){
        dist = max(dist, d[i]);
    }

    return dist;
}
/*
g++ -DEVAL -static -O2 -o dreaming grader.cpp dreaming.cpp
12 10 2
0 8 4 
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
2 6 2
10 4 2

12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3

*/

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:12:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i = 0; i < a.size(); i ++){
      |                    ~~^~~~~~~~~~
dreaming.cpp:26:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |             for(int i = 0; i < adj[node].size(); i ++){
      |                            ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp:31:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             for(int i = 0; i < v.size(); i ++){
      |                            ~~^~~~~~~~~~
dreaming.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int x = 0; x < components.size(); x ++){
      |                    ~~^~~~~~~~~~~~~~~~~~~
dreaming.cpp:62:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |                 for(int i = 0; i < adj[node].size(); i ++){
      |                                ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp:70:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for(int i = 0; i < visited.size(); i ++){
      |                        ~~^~~~~~~~~~~~~~~~
dreaming.cpp:87:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |                 for(int i = 0; i < adj[node].size(); i ++){
      |                                ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp:100:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for(int i = 0; i < visited.size(); i ++){
      |                        ~~^~~~~~~~~~~~~~~~
dreaming.cpp:119:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for(int i = 0; i < prefix.size(); i ++){
      |                        ~~^~~~~~~~~~~~~~~
dreaming.cpp:116:13: warning: unused variable 'score' [-Wunused-variable]
  116 |         int score = INT_MAX / 2;
      |             ^~~~~
dreaming.cpp:131:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for(int i = 0; i < maxsizes.size(); i ++){
      |                    ~~^~~~~~~~~~~~~~~~~
dreaming.cpp:138:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     for(int i = 0; i < centers.size(); i ++){
      |                    ~~^~~~~~~~~~~~~~~~
dreaming.cpp:157:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |             for(int i = 0; i < adj[node].size(); i ++){
      |                            ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp:165:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |     for(int i = 0; i < d.size(); i ++){
      |                    ~~^~~~~~~~~~
dreaming.cpp:180:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |             for(int i = 0; i < adj[node].size(); i ++){
      |                            ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp:188:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |     for(int i = 0; i < d.size(); i ++){
      |                    ~~^~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23