oj.uz

Submission #120176

# Submission time Handle Problem Language Result Execution time Memory
120176 2019-06-23T16:22:56 Z arthurconmy Islands (IOI08_islands) C++14
6 / 100
 274 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 + 1e5;
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 4 ms 2688 KB Output is correct
2 Runtime error 9 ms 5376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Correct 4 ms 2816 KB Output is correct
4 Runtime error 8 ms 5504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 274 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 273 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 270 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 8 ms 5376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 7 ms 5256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Incorrect 4 ms 2688 KB Output isn't correct
11 Runtime error 7 ms 5248 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 5 ms 2816 KB Output is correct
2 Runtime error 8 ms 5376 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 269 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 270 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 38 ms 8500 KB Output is correct
2 Runtime error 45 ms 16732 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 Runtime error 18 ms 8184 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 14828 KB Execution killed with signal 11 (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 7 ms 5120 KB Execution killed with signal 11 (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 15 ms 7808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -