oj.uz

답안 #1023810

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1023810 2024-07-15T06:51:12 Z dozer 꿈 (IOI13_dreaming) C++14
32 / 100
 47 ms 21584 KB 
#include <bits/stdc++.h>
using namespace std;
#include "dreaming.h"
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define mid (l + r) / 2
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
#define MAXN 300005


const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;


#define fail(s, x...) do { \
		fprintf(stderr, s "\n", ## x); \
		exit(1); \
	} while(0)

#define MAX_N 100000

int maks[MAXN], sub_maks[MAXN], vis[MAXN];
vector<pii> adj[MAXN];
int ANS;


int dfs2(int node, int root){
	int ans = 0;
	for (auto i : adj[node]){
		if (i.st == root) continue;
		ans = max(ans, dfs2(i.st, node) + i.nd);
	}
	return sub_maks[node] = ans;
}

int dfs(int node, int root, int m){
	vis[node] = 1;
	maks[node] = max(m, sub_maks[node]);
	int ans = maks[node];
	ANS = max(ans, ANS);
	vector<array<int, 3>> v;
	for (auto i : adj[node]){
		if (i.st == root) continue;
		v.pb({sub_maks[i.st] + i.nd, i.st, i.nd});
	}

	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++){
		int to = v[i][1], w = v[i][2];
		int add = m;
		if (i + 1 < v.size()) add = max(add, v.back()[0]);
		else add = max(add, v[v.size() - 2][0]);
		int neww = dfs(to, node, add + w);
		ans = min(ans, neww);
	}
	return ans;
}


int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	for (int i = 1; i <= N; i++){
		vis[i] = 0, adj[i].clear(), maks[i] = 0, sub_maks[i] = 0;
	}
    for (int i = 0; i < M; i++){
    	A[i]++, B[i]++;
    	adj[A[i]].pb({B[i], T[i]});
    	adj[B[i]].pb({A[i], T[i]});
    }

    ANS = 0;
    priority_queue<int> q;
    for (int i = 1; i <= N; i++){
    	if (vis[i]) continue;
    	int tmp = dfs2(i, 0);
    	int to = dfs(i, 0, 0);
    	q.push(to);
    }

    while(!q.empty()){
    	int a = q.top();
    	q.pop();
    	if (q.empty()) break;
    	int b = q.top();
    	q.pop();
    	int neww = max(a, b + L);
    	ANS = max(ANS, a + b + L);
    	q.push(neww);
    }

    return ANS;
}

Compilation message

dreaming.cpp: In function 'int dfs(int, int, int)':
dreaming.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for (int i = 0; i < v.size(); i++){
      |                  ~~^~~~~~~~~~
dreaming.cpp:59:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   if (i + 1 < v.size()) add = max(add, v.back()[0]);
      |       ~~~~~~^~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:82:10: warning: unused variable 'tmp' [-Wunused-variable]
   82 |      int tmp = dfs2(i, 0);
      |          ^~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 21584 KB Output is correct
2 Correct 35 ms 20820 KB Output is correct
3 Correct 29 ms 19544 KB Output is correct
4 Correct 9 ms 9308 KB Output is correct
5 Correct 7 ms 8536 KB Output is correct
6 Correct 11 ms 10588 KB Output is correct
7 Correct 3 ms 7496 KB Output is correct
8 Correct 20 ms 13036 KB Output is correct
9 Correct 25 ms 16988 KB Output is correct
10 Correct 3 ms 7512 KB Output is correct
11 Correct 39 ms 17492 KB Output is correct
12 Correct 47 ms 19544 KB Output is correct
13 Correct 3 ms 7512 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Incorrect 3 ms 7516 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 21584 KB Output is correct
2 Correct 35 ms 20820 KB Output is correct
3 Correct 29 ms 19544 KB Output is correct
4 Correct 9 ms 9308 KB Output is correct
5 Correct 7 ms 8536 KB Output is correct
6 Correct 11 ms 10588 KB Output is correct
7 Correct 3 ms 7496 KB Output is correct
8 Correct 20 ms 13036 KB Output is correct
9 Correct 25 ms 16988 KB Output is correct
10 Correct 3 ms 7512 KB Output is correct
11 Correct 39 ms 17492 KB Output is correct
12 Correct 47 ms 19544 KB Output is correct
13 Correct 3 ms 7512 KB Output is correct
14 Correct 3 ms 7516 KB Output is correct
15 Correct 3 ms 7516 KB Output is correct
16 Incorrect 3 ms 7516 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 11608 KB Output is correct
2 Correct 20 ms 11736 KB Output is correct
3 Correct 22 ms 11608 KB Output is correct
4 Correct 20 ms 11748 KB Output is correct
5 Correct 29 ms 11612 KB Output is correct
6 Correct 32 ms 11996 KB Output is correct
7 Correct 26 ms 11868 KB Output is correct
8 Correct 21 ms 11864 KB Output is correct
9 Correct 22 ms 11612 KB Output is correct
10 Correct 22 ms 11868 KB Output is correct
11 Correct 4 ms 7516 KB Output is correct
12 Correct 10 ms 9176 KB Output is correct
13 Correct 10 ms 9128 KB Output is correct
14 Correct 11 ms 9176 KB Output is correct
15 Correct 10 ms 9160 KB Output is correct
16 Correct 10 ms 9176 KB Output is correct
17 Correct 10 ms 9176 KB Output is correct
18 Correct 13 ms 9168 KB Output is correct
19 Correct 10 ms 9176 KB Output is correct
20 Correct 4 ms 7260 KB Output is correct
21 Correct 3 ms 7260 KB Output is correct
22 Correct 4 ms 7516 KB Output is correct
23 Correct 11 ms 9164 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Incorrect 3 ms 7516 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 21584 KB Output is correct
2 Correct 35 ms 20820 KB Output is correct
3 Correct 29 ms 19544 KB Output is correct
4 Correct 9 ms 9308 KB Output is correct
5 Correct 7 ms 8536 KB Output is correct
6 Correct 11 ms 10588 KB Output is correct
7 Correct 3 ms 7496 KB Output is correct
8 Correct 20 ms 13036 KB Output is correct
9 Correct 25 ms 16988 KB Output is correct
10 Correct 3 ms 7512 KB Output is correct
11 Correct 39 ms 17492 KB Output is correct
12 Correct 47 ms 19544 KB Output is correct
13 Correct 3 ms 7512 KB Output is correct
14 Correct 3 ms 7516 KB Output is correct
15 Correct 3 ms 7516 KB Output is correct
16 Incorrect 3 ms 7516 KB Output isn't correct
17 Halted 0 ms 0 KB -