oj.uz

Submission #703020

# Submission time Handle Problem Language Result Execution time Memory
703020 2023-02-25T15:45:12 Z vuk_ Dreaming (IOI13_dreaming) C++17
18 / 100
 1000 ms 30840 KB 
#pragma once
 
#include "dreaming.h"
 
#include <bits/stdc++.h>
using namespace std;
 
// Loops
#define FOR(n)              for(int i=0;i<n;i++)
#define FORJ(n)             for(int j=0;j<n;j++)
#define FORN(n,x)           for(int x=0;i<n;i++)
#define RFOR(n)             for(int i=n-1;i>=0;i--)
#define RFORN(n,x)          for(int x=n-1;x>=0;x--)
#define ODD_FOR(n)          for(int i=1;i<n;i+=2)
#define EVEN_FOR(n)         for(int i=2;i<n;i+=2)
#define FROM(n,m)           for(int i=n;i<m;i++)
#define FROMJ(n,m)          for(int j=n;j<m;j++)
#define RFROM(n,m)          for(int i=n-1;i>=m;i--)
#define RFROMJ(n,m)         for(int j=n-1;j>=m;j--)
#define STL_FOR(a)          for(auto i=a.begin();i!=a.end();i++)
#define STL_FORJ(a)         for(auto j=a.begin();j!=a.end();j++)
#define STL_FORN(a,x)       for(auto x=a.begin();x!=a.end();x++)
#define STL_FROM(a,n,m)     for(auto i=n;i!=m;i++)
#define STL_FROMJ(n,m)      for(auto j=n;j!=m;j++)
#define RSTL_FOR(a)         for(auto i=a.rbegin();i!=a.rend();i++)
#define RSTL_FORJ(a)        for(auto j=a.rbegin();j!=a.rend();j++)
 
// Types
#define ll             long long int
#define vec                   vector
#define veci             vector<int>
#define pb                 push_back
#define pf                push_front
#define fi                     first
#define se                    second
#define umap           unordered_map
#define ummap     unordered_multimap
#define mmap                multimap
#define mset                multiset
#define uset           unordered_set
#define umset     unordered_multiset
#define endl                    '\n'
#define all(a)    a.begin(), a.end()
 
// I/O
void read() {}
template<typename type, typename... types>
void read(type& arg, types&... args) { cin >> arg; read(args...); }
 
void write() { cout << endl; }
template<typename type, typename... types>
void write(type arg, types... args) { cout << arg << ' '; write(args...); }
 
#define dbg(x) cerr<<#x<<" = "<<x<<endl;
 
struct weighted_edge {
    int edge, weight;
};
 
struct graph {
    int n, m;
    list<weighted_edge>* adj;
 
    graph(int n, int m)
        :n(n), m(m)
    {
        adj = new list<weighted_edge>[n];
    }
    ~graph() { delete[] adj; }
 
    void add_edge(int node, int edge, int weight) {
        adj[node].push_back({ edge, weight });
        adj[edge].push_back({ node, weight });
    }
 
    friend istream& operator>> (istream& in, graph& g) {
        int node, edge, weight;
        for (int i = 0; i < g.m; i++) {
            in >> node >> edge >> weight;
            g.add_edge(node, edge, weight);
        }
 
        return in;
    }
};
 
const int M = 1e6;
struct node_dist {
    int node, dist = 0;
};
struct two_max {
    node_dist fi, se;
 
    void add(int n, int d) {
        if (fi.dist < d) {
            se = fi;
            fi = { n, d };
        }
        else if (se.dist < d) {
            se = { n, d };
        }
    }
};
two_max node_max_dist[M];
int graph_min_dist = INT_MAX;
int graph_min_node = -1;
int max_dist=-1;

bool seen[M] = {};
 
int billabong_front(graph& g, int node, int edge) {
    seen[edge] = true;
    for (weighted_edge x : g.adj[edge]) {
        if (x.edge != node) {
            node_max_dist[edge].add(x.edge, billabong_front(g, edge, x.edge) + x.weight);
        }
    }
 
    return node_max_dist[edge].fi.dist;
}
 
void billabong_back(graph& g, int node, int edge) {
 
    if (graph_min_dist > node_max_dist[edge].fi.dist) {
        graph_min_dist = node_max_dist[edge].fi.dist;
        graph_min_node = edge;
    }
 
    for (weighted_edge x : g.adj[edge]) {
        if (x.edge != node) {
 
            if (node_max_dist[edge].fi.node != x.edge) {
                node_max_dist[x.edge].add(edge, node_max_dist[edge].fi.dist + x.weight);
            }
            else {
                node_max_dist[x.edge].add(edge, node_max_dist[edge].se.dist + x.weight);
            }
            max_dist=max(max_dist, node_max_dist[x.edge].fi.dist+node_max_dist[x.edge].se.dist);
            billabong_back(g, edge, x.edge);

            billabong_back(g, edge, x.edge);
        }
    }
}
 
inline void billabong(graph& g, int node) {
    billabong_front(g, -1, node);
    billabong_back(g, -1, node);
}
 
void insert(int a[3], int x) {
    if (a[0] < x) {
        a[2] = a[1];
        a[1] = a[0];
        a[0] = x;
    }
    else if (a[1] < x) {
        a[2] = a[1];
        a[1] = x;
    }
    else if (a[2] < x) {
        a[2] = x;
    }
}
 
int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
    graph g(n, m);
    FOR(m) {
        g.add_edge(A[i], B[i], T[i]);
    }
    int a[3] = { -l, -l, -l };
    FOR(n) {
        if (!seen[i]) {
            graph_min_dist = INT_MAX;
            billabong(g, i);
            insert(a, graph_min_dist);
        }
    }
    return max(max_dist, max(a[0]+a[1]+l, a[1]+a[2]+l+l));
}

Compilation message

dreaming.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 20948 KB Output is correct
2 Correct 25 ms 20968 KB Output is correct
3 Correct 24 ms 20916 KB Output is correct
4 Correct 31 ms 20964 KB Output is correct
5 Correct 24 ms 20940 KB Output is correct
6 Correct 29 ms 21196 KB Output is correct
7 Correct 28 ms 21204 KB Output is correct
8 Correct 24 ms 20828 KB Output is correct
9 Correct 22 ms 20780 KB Output is correct
10 Correct 24 ms 21204 KB Output is correct
11 Correct 7 ms 15900 KB Output is correct
12 Correct 9 ms 18396 KB Output is correct
13 Correct 11 ms 18408 KB Output is correct
14 Correct 10 ms 18388 KB Output is correct
15 Correct 10 ms 18388 KB Output is correct
16 Correct 10 ms 18388 KB Output is correct
17 Correct 10 ms 18388 KB Output is correct
18 Correct 10 ms 18388 KB Output is correct
19 Correct 11 ms 18368 KB Output is correct
20 Correct 8 ms 15932 KB Output is correct
21 Correct 8 ms 15904 KB Output is correct
22 Correct 7 ms 15964 KB Output is correct
23 Correct 10 ms 18376 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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