oj.uz

Submission #120174

# Submission time Handle Problem Language Result Execution time Memory
120174 2019-06-23T16:21:35 Z arthurconmy Islands (IOI08_islands) C++14
6 / 100
 428 ms 131072 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
#include <chrono>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef pair<int,int> pii;
#define REP(i, a, b) for (int i = int(a); i <= int(b); i++)
#define REPb(j, d, c) for (int j = int(d); j >= int(c); j--)
#define ff first
#define ss second
#define pb push_back
#define len(x) int((x).size())
#define endl "\n"

const int MAXN=1 + 1e6;
int n;
tuple<int,int,int> edges[MAXN];
vector<tuple<int,int,int>> adj[MAXN]; // destination edge, length, edge no.
bool edge_used[MAXN];
int cycle_edge;
bool vis1[MAXN];
bool in_cycle[MAXN];
int length_to[MAXN];
vector<int> cur_comp;

void connect_dfs(int v)
{
	for(auto u:adj[v])
	{
		if(vis1[get<0>(u)])
		{
			if(!edge_used[get<2>(u)] && cycle_edge==-1) cycle_edge=get<2>(u);
			continue;
		}
			
		cur_comp.pb(get<0>(u));
		vis1[get<0>(u)]=true;
		edge_used[get<2>(u)]=true;
		connect_dfs(get<0>(u));
	}
}

/*

7
3 8
7 2
4 2
1 4
1 9
3 4
2 3 

*/

int main() // LL OR INT?? DELETED IFSTREAM??
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	//ifstream cin("input.txt");
	//ifstream cin("test.in");
	//ofstream cout("test.out");

	// take input

	cin>>n;

	REP(u,1,n)
	{
		int v, l;
		cin>>v>>l;

		adj[u].pb({v,l,u});
		adj[v].pb({u,l,u});
	
		edges[u]={u,v,l};
	}

	ll ans=0;

	REP(i,1,n)
	{
		// for connected component

		//		find cycle

		if(vis1[i]) continue;

		cur_comp.clear();
		cur_comp.pb(i);
		vis1[i]=true;
		cycle_edge=-1;
		connect_dfs(i);

		// for(auto v:cur_comp) cout << v << " ";
		// cout << endl;
	
		// find simple path between vertices of the cycle edge in the tree excepting the cycle edge

		vi parent(cur_comp.size()+1);

		vi BFS = {get<0>(edges[cycle_edge])};

		while(!BFS.empty())
		{
			vi new_BFS;

			for(auto u:BFS)
			{
				for(auto v:adj[u])
				{
					if(get<2>(v)==cycle_edge || parent[get<0>(v)]) continue;

					parent[get<0>(v)] = u;
					length_to[get<0>(v)] = get<1>(v);
					new_BFS.pb(get<0>(v));
				}
			}

			BFS=new_BFS;
		}

		vi cycle={get<1>(edges[cycle_edge])}; // this is kinda done in reverse...
		in_cycle[cycle[0]]=true;

		vector<int> path_len;

		while(cycle.back() != get<0>(edges[cycle_edge]))
		{
			path_len.pb(length_to[cycle.back()]);

			cycle.pb(parent[cycle.back()]);
			in_cycle[cycle.back()]=true;
		}

		path_len.pb(get<2>(edges[cycle_edge]));

		// for(auto c:cycle) cout << c << " ";
		// cout << endl;

		// for(auto pl:path_len) cout << pl << " ";
		// cout << endl << endl;

		// 		for each branch

		vector<ll> branch_len(cycle.size());

		REP(i,0,cycle.size()-1)
		{
			vector<pair<int,ll>> BFS2 = {{cycle[i],0}};

			ll max_dis=0;
		
			while(!BFS2.empty())
			{
				vector<pair<int,ll>> new_BFS2;

				for(auto u:BFS2)
				{
					for(auto v:adj[u.ff])
					{
						int vert = get<0>(v);

						if(in_cycle[vert]) continue;
						in_cycle[vert]=true;

						max_dis=max(max_dis,u.ss + get<1>(v));

						new_BFS2.pb({vert, u.ss + get<1>(v)});
					}
				}

				BFS2=new_BFS2;
			}

			// cout << cycle[i] << " " << max_dis << endl;
			branch_len[i] = max_dis;
		}

		//		do the PQ DP thing

		priority_queue<pair<ll,int>> endps;
		ll lap=0;

		ll max_trip=0;

		REP(i,0,cycle.size()-1)
		{
			if(i>0) lap+=path_len[i-1];
			if(!endps.empty()) max_trip=max(max_trip,endps.top().ff+branch_len[i]+lap);

			endps.push({branch_len[i]-lap,i});

			// cout << i << " " << max_trip << endl;
		}

		lap+=path_len.back();

		REP(i,0,cycle.size()-1)
		{
			while(!endps.empty() && endps.top().ss<=i) endps.pop();

			if(i>0) lap+=path_len[i-1];

			if(!endps.empty()) max_trip=max(max_trip,endps.top().ff+branch_len[i]+lap);
		}

		// cout << "MAX_TRIP: "  << max_trip << endl;
		ans += max_trip;
	}

	//			find length

	// gravy

	cout << ans << endl;
}

Subtask #1
6.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23928 KB Output is correct
2 Runtime error 46 ms 47868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Correct 21 ms 23936 KB Output is correct
4 Runtime error 47 ms 47608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 280 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 262 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 256 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 50 ms 47780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 48 ms 47608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Incorrect 22 ms 23808 KB Output isn't correct
11 Runtime error 46 ms 47608 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23936 KB Output is correct
2 Runtime error 48 ms 47736 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 262 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 262 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 30516 KB Output is correct
2 Runtime error 87 ms 60380 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 42420 KB Output is correct
2 Runtime error 168 ms 83564 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 298 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 402 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 428 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -