Submission #702084

#	Time	Username	Problem	Language	Result	Execution time	Memory
702084		vuk_	Dreaming (IOI13_dreaming)	C++17	18 / 100	58 ms	30932 KiB

dreaming

#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;

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);
			}
			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(a[0] + a[1] + l, a[1] + a[2] + l + l);
}

Compilation message (stderr)

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

• Subtask 1: 0 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 18 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23