Submission #394092

#	Time	Username	Problem	Language	Result	Execution time	Memory
394092		junodeveloper	Dreaming (IOI13_dreaming)	C++17	Compilation error	0 ms	0 KiB

dreaming

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
int n, m, L, r1, r2;
int D[100010];
bool vis[100010];
vector<pair<int,int> > adj[100010];
void dfs1(int p, int u) {
	vis[u] = 1;
	for(auto& it : adj[u])
		if(it.first != p) {
			dfs1(u, it.first);
			D[u] = max(D[u], D[it.first] + it.second);
		}
}
void dfs2(int p, int u, int E) {
	r1 = min(r1, max(D[u], E));
	int mx[2] = {-1,-1}, idx[2]={-1,-1};
	for(auto& it : adj[u])
		if(it.first != p) {
			int val = D[it.first] + it.second;
			if(val > mx[0]) mx[1] = mx[0], idx[1] = idx[0], mx[0] = val, idx[0] = it.first;
			else if(val > mx[1]) mx[1] = val, idx[1] = it.first;
		}
	r2 = max(r2, D[u]);
	if(mx[0]!=-1&&mx[1]!=-1) r2 = max(r2, mx[0] + mx[1]);
	for(auto& it : adj[u]) {
		if(it.first == p) continue;
		if(idx[0] != it.first) dfs2(u, it.first, it.second + max(E, mx[0]));
		else dfs2(u, it.first, it.second + max(E, mx[1]));
	}
}
int main() {
	scanf("%d%d%d", &n, &m, &L);
	for(int i=0; i<m; i++) {
		int u,v,c;
		scanf("%d%d%d",&u,&v,&c);
		adj[u].push_back({v,c});
		adj[v].push_back({u,c});
	}
	vector<int> va;
	int res = 0;
	for(int i=0; i<n; i++) {
		if(vis[i]) continue;
		r1 = 1e9; r2 = 0;
		dfs1(i,i);
		dfs2(i,i,0);
		va.push_back(r1);
		res = max(res, r2);
	}
	sort(all(va));
	if(sz(va)>=2) res = max(res, va[sz(va)-2] + va.back() + L);
	if(sz(va)>=3) res = max(res, va[sz(va)-3] + va[sz(va)-2] + 2 * L);
	printf("%d", res);
	return 0;
}

Compilation message (stderr)

dreaming.cpp: In function 'int main()':
dreaming.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |  scanf("%d%d%d", &n, &m, &L);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |   scanf("%d%d%d",&u,&v,&c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
/tmp/ccn8Rv2Y.o: In function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccS1SEuo.o:grader.c:(.text.startup+0x0): first defined here
/tmp/ccS1SEuo.o: In function `main':
grader.c:(.text.startup+0xc9): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status