Submission #454614

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
454614	2021-08-05T06:37:04 Z	Shin	Dreaming (IOI13_dreaming)	C++14	Compilation error	0 ms	0 KB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
#define fi first
#define se second
#define TASK "file"

using namespace std;
const int N = 2e5 + 7;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const long long INFLL = 1e18 + 7;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    return 42;
}


int n, m, k;
int res;
int g[N];
int f[2][N];
vector<int> gNew[N];
vector<pair<int, int>> adj[N];
vector<pair<int, int>> center_node;
pair<int, int> center;

void load_tree(void) {
	cin >> n >> m >> k;
	for (int i = 1; i <= m; i ++) {
		int u, v, w; 
		cin >> u >> v >> w;
		u ++; v ++;
		adj[u].push_back(make_pair(v, w));
		adj[v].push_back(make_pair(u, w));
	}
}

void dfs1(int u, int p) {
	for (pair<int, int> v: adj[u]) if (v.fi != p) {
		dfs1(v.fi, u);
		if (f[0][u] <= f[0][v.fi] + v.se) {
			f[1][u] = f[0][u];
			f[0][u] = f[0][v.fi] + v.se;
		} else
			maximize(f[1][u], f[0][v.fi] + v.se);
	}
}

void dfs2(int u, int p, int dist) {
	g[u] = dist;
	for (pair<int, int> v: adj[u]) if (v.fi != p) {
		if (f[0][u] == f[0][v.fi] + v.se)
			dfs2(v.fi, u, max(dist, f[1][u]) + v.se);
		else
			dfs2(v.fi, u, max(dist, f[0][u]) + v.se);
	}
	minimize(center, make_pair(max(dist, f[0][u]), u));
}

void dfs(int u, int p) {
	for (pair<int, int> v: adj[u]) if (v.fi != p) {
		dfs(v.fi, u);
		if (f[0][u] <= f[0][v.fi] + v.se) {
			f[1][u] = f[0][u];
			f[0][u] = f[0][v.fi] + v.se;
		} else
			maximize(f[1][u], f[0][v.fi] + v.se);
	}
	maximize(res, f[0][u] + f[1][u]);
}

void solve(void) {
	memset(g, -1, sizeof g);
	for (int i = 1; i <= n; i ++) if (g[i] < 0) {
		dfs1(i, i);
		center = make_pair(INF, 0);
		dfs2(i, i, 0);
		center_node.push_back(center);
	}
	sort(center_node.begin(), center_node.end(), greater<pair<int, int>>());
	for (int i = 1; i < center_node.size(); i ++) {
		adj[center_node[0].se].push_back(make_pair(center_node[i].se, k));
		adj[center_node[i].se].push_back(make_pair(center_node[0].se, k));
	}
	res = 0;
	memset(f, 0, sizeof f);
	dfs(1, 1);
	cout << res;
}

int main(void) {
    ios_base::sync_with_stdio(0); 
    cin.tie(0);
    
    int test = 1;
    // cin >> test;
    while (test --) {
    	load_tree();
        solve();
    }
    return 0;
}

Compilation message

dreaming.cpp: In function 'void solve()':
dreaming.cpp:93:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for (int i = 1; i < center_node.size(); i ++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccDROrcf.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc41a1tf.o:grader.c:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status