oj.uz

Submission #126749

# Submission time Handle Problem Language Result Execution time Memory
126749 2019-07-08T10:42:28 Z groeneprof Islands (IOI08_islands) C++14
80 / 100
 1748 ms 131076 KB 
#include <bits/stdc++.h>
#define P(x) do {if(debug) cout << x << endl;} while(false)
#define H(x) P(#x << ": " << x)
#define FR(i, a, b) for(int i = (a); i < (b); ++i)
#define F(i, n) FR(i, 0, n)
#define DR(i, a, b) for(int i = (b); i --> (a);)
#define D(i, n) DR(i, 0, n)
#define S(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()
#define MI(x, a) (x) = min(x, a)
#define MA(x, a) (x) = max(x, a)
#define V vector
#define pb push_back
#define mp make_pair
using namespace std;
const bool debug = 0;
const long long inf = 1e18;


struct edge
{
	int u, v, w;
	bool operator== (edge o){
		return u == o.u && v == o.v && w == o.w;
	}
	bool operator!= (edge o){
		return !(*this == o);
	}
};

struct sliding_maximum
{
	deque<pair<long long, int> > qu;
	int i, l;
	sliding_maximum(int _l){
		i = 0;
		l = _l;
	}
	long long getmax(){
		if(qu.empty()) return -inf;
		return qu.front().first;
	}	
	void slide(long long newval){
		while(!qu.empty()&&newval > qu.back().first){
			qu.pop_back();
		}
		qu.push_back({newval,i});
		if(qu.front().second<=i-l){
			qu.pop_front();
		}
		i++;
	}
};

int N;
vector<edge> edgelist; //12 MB
vector<vector<int> > graph; //8 MB (16 MB worst case)?
vector<bool> vis; //1 MB

bool flag = false;
int dfs(int id, vector<int>& cycle){
	edge p = edgelist[id];
	H(p.u); H(p.v); H(p.w);
	//F(ii, 1e8);
	if(vis[p.v]&&flag){
		P("return 1");
		return -1;
	}
	if(vis[p.v]){
		flag = true;
		P("return 2");
		P("cyclee: "<<p.v);
		H(id);
		cycle.push_back(id);
		return p.v;
	}
	vis[p.v] = true;
	int ce = -1;
	for(int i : graph[p.v]) if(id != (i^1)) {
		int a = dfs(i, cycle);
		if(a!=-1) ce = a;
	}
	if(ce == p.v){
		//cycle.push_back(cycle[0]);
		P("return 3");
		return -1; 
	}
	if(ce != -1){
		P("cycle: "<<p.v);
		H(id);
		cycle.push_back(id);
	}
	P("return 4: "<<ce);
	return ce;
}

int f1, f2;
long long _maxu, _maxd;

void dfs2(int id, long long d){
	//F(i, 1e8);
	//edge p = edgelist[id];
	//H(p.u); H(p.v); H(p.w);
	//H(id); H(f1); H(f2);
	if(d>_maxd){
		_maxu = edgelist[id].v;
		_maxd = d;
		P("update (maxu, maxd) to");
		H(_maxu); H(_maxd);
	}
	//int d = 0;
	for(int i : graph[edgelist[id].v]) if(i-i%2 != id-id%2 && i-i%2 != f1-f1%2 && i-i%2 != f2-f2%2){
		dfs2(i, d+edgelist[i].w);
	}
	//return d+p.w;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//input
	cin>>N;
	edgelist.resize(2*N+1);
	graph.resize(N);
	F(u, N){
		int v,w;
		cin>>v>>w;
		v--;
		edgelist[2*u] = {u, v, w};
		graph[u].push_back(2*u);
		edgelist[2*u+1] = {v, u, w};
		graph[v].push_back(2*u+1);

	}

	//loop to calculate everything
	vis.resize(N, 0);
	edgelist[2*N] = {-1, 0, 0};
	long long sum = 0;

	F(t, N) if(!vis[t]){
		P("--------------------------------------------");
		H(t);
		long long maxtot = 0;
		vector<int> cycle; //4MB
		flag = false;
		edgelist[2*N].v = t;
		dfs(2*N, cycle);
		int c = cycle.size();
		reverse(cycle.begin(), cycle.end()); //(0,1), (1,2), ..., (c-1, 0)
		P("step 1");
		for(int i : cycle){
			edge p = edgelist[i];
			P("cycle edge "<<i);
			H(p.u);
			H(p.v);
			H(p.w);
		}

		vector<long long> d(c, 0); //8MB
		F(i, c){
			H(i);
			edge p = edgelist[cycle[i]];
			f1 = cycle[(i-1+c)%c];
			f2 = cycle[i];
			edgelist[2*N].v = p.u;
			//long long maxu = -1, maxd = -1;
			P("root: "<<p.u);
			_maxu = -1;
			_maxd = -1;
			dfs2(2*N, 0);
			d[i] = _maxd;
			//long long maxu2 = -1, maxd2 = -1;
			edgelist[2*N].v = _maxu;
			_maxu = -1; _maxd = -1;
			//P("root2: "<<maxu);

			dfs2(2*N, 0);
			maxtot = max(maxtot, _maxd);
		}
		H(maxtot);
		P("step 2");

		//vector<long long> pref(c*2+1, 0);
		long long csum = 0;
		F(i, 2*c-1){
			//pref[i+1] = pref[i] + edgelist[cycle[i%c]].w;
			csum = csum + edgelist[cycle[i%c]].w;
		}
		//csum == pref(c*2-1)
		P("step 3");

		sliding_maximum sm(c-1);
		H(c);
		for(int i = 2*c-1; i>=0; i--){
			H(i);
			maxtot = max((long long)maxtot, sm.getmax()-csum+d[i%c]);
			sm.slide(csum+d[i%c]);
			csum -= edgelist[cycle[(i+c-1)%c]].w;
		}
		P("step 4");
		H(maxtot);
		sum += maxtot;

	}
	cout<<sum<<endl;
	return 0;
}

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 348 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 4 ms 888 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1912 KB Output is correct
2 Correct 28 ms 4728 KB Output is correct
3 Correct 17 ms 2296 KB Output is correct
4 Correct 10 ms 1272 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 6500 KB Output is correct
2 Correct 57 ms 11024 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 20344 KB Output is correct
2 Correct 144 ms 27480 KB Output is correct
3 Correct 163 ms 37356 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 38520 KB Output is correct
2 Correct 278 ms 60548 KB Output is correct
3 Correct 321 ms 76600 KB Output is correct
4 Correct 389 ms 95208 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 98256 KB Output is correct
2 Correct 1140 ms 131072 KB Output is correct
3 Correct 407 ms 75548 KB Output is correct
4 Correct 559 ms 114408 KB Output is correct
5 Correct 543 ms 114044 KB Output is correct
6 Correct 1748 ms 91180 KB Output is correct
7 Runtime error 589 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #9
0 / 10.0

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