oj.uz

Submission #725334

# Submission time Handle Problem Language Result Execution time Memory
725334 2023-04-17T09:49:32 Z yeyso Dreaming (IOI13_dreaming) C++14
14 / 100
 1000 ms 16580 KB 
#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;
    for(int x = 0; x < components.size(); x ++){
        prefix = prefix0;
        int furtherest = 0; int dist = 0;
        d = d0; visited = v0;
        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);
        //cout << furtherest << "\n";
        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]);
                }
            }
        }
        
        for(int i = 0; i < visited.size(); i ++){
            if(visited[i]){
                // DISTANCE THEN NODE
                prefix.push_back({d[i], i});
                //cout << d[i] << " ";
            }
        }
        //cout << "\n";
        sort(prefix.begin(), prefix.end());
        //cout << components[x] << " | ";
        int maxd = prefix[prefix.size() - 1].first;
        int score = INT_MAX / 2;
        int best = INT_MAX / 2;
        for(int i = 0; i < prefix.size(); i ++){
            //cout << prefix[i].first << " ";
            if(max(prefix[i].first, maxd - prefix[i].first) < best){
                //score = abs(maxd / 2 - prefix[i].first);
                best = max(prefix[i].first, maxd - prefix[i].first);
            }
        }
        //prefixes.push_back(prefix);
        maxsizes.push_back(maxd);
        //cout << " - " << best << " ";
        csize.push_back(best);
        //cout << best << "\n";
        //cout << furtherest << " " << dist << " " << components[i] << "\n";
        //cout << components[i] << " ";
    }

    
    return max(max(maxsizes[0], maxsizes[1]), csize[0] + csize[1] + l);
}
/*
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
*/

Compilation message

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:47:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int x = 0; x < components.size(); x ++){
      |                    ~~^~~~~~~~~~~~~~~~~~~
dreaming.cpp:59:34: 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 < adj[node].size(); i ++){
      |                                ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp:66:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(int i = 0; i < visited.size(); i ++){
      |                        ~~^~~~~~~~~~~~~~~~
dreaming.cpp:86:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |                 for(int i = 0; i < adj[node].size(); i ++){
      |                                ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp:94:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for(int i = 0; i < visited.size(); i ++){
      |                        ~~^~~~~~~~~~~~~~~~
dreaming.cpp:107: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]
  107 |         for(int i = 0; i < prefix.size(); i ++){
      |                        ~~^~~~~~~~~~~~~~~
dreaming.cpp:105:13: warning: unused variable 'score' [-Wunused-variable]
  105 |         int score = INT_MAX / 2;
      |             ^~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 16528 KB Output is correct
2 Correct 85 ms 16580 KB Output is correct
3 Correct 61 ms 11012 KB Output is correct
4 Correct 11 ms 2752 KB Output is correct
5 Correct 9 ms 1988 KB Output is correct
6 Correct 19 ms 4052 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 56 ms 7360 KB Output is correct
9 Correct 54 ms 9276 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 119 ms 12792 KB Output is correct
12 Correct 103 ms 14796 KB Output is correct
13 Correct 1 ms 468 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 16528 KB Output is correct
2 Correct 85 ms 16580 KB Output is correct
3 Correct 61 ms 11012 KB Output is correct
4 Correct 11 ms 2752 KB Output is correct
5 Correct 9 ms 1988 KB Output is correct
6 Correct 19 ms 4052 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 56 ms 7360 KB Output is correct
9 Correct 54 ms 9276 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 119 ms 12792 KB Output is correct
12 Correct 103 ms 14796 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 312 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Incorrect 1 ms 212 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 16528 KB Output is correct
2 Correct 85 ms 16580 KB Output is correct
3 Correct 61 ms 11012 KB Output is correct
4 Correct 11 ms 2752 KB Output is correct
5 Correct 9 ms 1988 KB Output is correct
6 Correct 19 ms 4052 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 56 ms 7360 KB Output is correct
9 Correct 54 ms 9276 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 119 ms 12792 KB Output is correct
12 Correct 103 ms 14796 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 312 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Incorrect 1 ms 212 KB Output isn't correct
17 Halted 0 ms 0 KB -