oj.uz

답안 #737852

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
737852 2023-05-07T20:47:50 Z BidoTeima 꿈 (IOI13_dreaming) C++17
0 / 100
 54 ms 28024 KB 
/*
ID: BidoTeima
LANG: C++11
TASK:
*/
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
using ll = long long; 
void moo(string filename);
void ACPLS(string str = "")
{
    if(str=="NOF")return;
    if(str.size() && str != "IIOT")
        moo(str);
    else if(str != "IIOT"){
#ifndef ONLINE_JUDGE
        freopen("output.txt", "w", stdout);
        freopen("input.txt", "r", stdin);
#endif
    }
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
void moo(string fileName){
    freopen((fileName+".in").c_str(),"r",stdin);
    freopen((fileName+".out").c_str(),"w",stdout);
}
#define tcccc         \
    int tttttt/*,subtask*/;    \
    cin >> tttttt/* >> subtask*/; \
    while (tttttt--)/*end
*/ 
const int N = 1e5;
vector<pair<int,int>> adj[N];  
int cur_farthest_node, cur_farthest_node_dist;
bool vis[N];
vector<int>cc;
void set_farthest_node(int node, int prev, int cur_dist){
    vis[node] = 1;
    cc.push_back(node);
    if(adj[node].empty() || (adj[node].size() == 1 && prev != -1)){
        if(cur_dist > cur_farthest_node_dist){
            cur_farthest_node_dist = cur_dist;
            cur_farthest_node = node;
        }
        return;
    }
    for(auto& edge : adj[node]){
        if(edge.first != prev){
            set_farthest_node(edge.first, node, cur_dist + edge.second);
        }
    }
}
int dist[N][2];
void precompute_dist_dfs(int node, int prev, int cur_dist, bool b){
    dist[node][b] = cur_dist;
    for(auto& edge : adj[node]){
        if(edge.first != prev){
            precompute_dist_dfs(edge.first, node, cur_dist + edge.second, b);
        }
    }
}
void precompute_dist(int node, bool b){
    for(int i : cc)
        dist[i][b] = 1e9;
    precompute_dist_dfs(node, -1, 0, b);
}
int travelTime(int n, int m, int l, int a[], int b[], int t[])
{      
    for(int i = 0; i < m; i++){ 
        adj[a[i]].push_back({b[i], t[i]});
        adj[b[i]].push_back({a[i], t[i]});
    }
    multiset<pair<int, int>>ms;
    for(int i = 0; i < n; i++){
        if(vis[i])
            continue;
        cc.clear();
        cur_farthest_node_dist = -1;
        set_farthest_node(i, -1, 0);
        int e1 = cur_farthest_node;
        cur_farthest_node_dist = -1;
        set_farthest_node(e1, -1, 0);
        int e2 = cur_farthest_node;
        precompute_dist(e1, 0);
        precompute_dist(e2, 1);
        int root = e1, min_max_dist = dist[e2][0];
        assert(dist[e2][0] == dist[e1][1]); 
        for(int node : cc){
            if(max(dist[node][0], dist[node][1]) < min_max_dist){
                min_max_dist = max(dist[node][0], dist[node][1]);
                root = node;
            }
        }
        ms.insert({min_max_dist, dist[e2][0]});
    }
    while(ms.size() != 1){
        auto it1 = ms.begin(), it2 = next(ms.begin());
        int a = it1->first, b = it2->first, d1 = it1->second, d2 = it2->second;
        ms.erase(ms.begin());
        ms.erase(next(ms.begin()));
        ms.insert({max(b, a + l), max({d1, d2, a + b + l})});
    }
    return ms.begin()->second;
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:89:13: warning: variable 'root' set but not used [-Wunused-but-set-variable]
   89 |         int root = e1, min_max_dist = dist[e2][0];
      |             ^~~~
dreaming.cpp: In function 'void ACPLS(std::string)':
dreaming.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void moo(std::string)':
dreaming.cpp:27:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     freopen((fileName+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:28:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     freopen((fileName+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 54 ms 28024 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 5204 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 54 ms 28024 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 41 ms 17500 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 5204 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 54 ms 28024 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -