oj.uz

답안 #126420

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
126420 2019-07-07T16:59:13 Z groeneprof Islands (IOI08_islands) C++14
18 / 100
 1354 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;
}

void dfs2(int id, int d, int& f1, int& f2, int& maxu, int& maxd){
	//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 = p.v;
		maxd = d;
		P("update (maxu, maxd) to");
		H(maxu); H(maxd);
	}
	//int d = 0;
	for(int i : graph[p.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, f1, f2, maxu, maxd);
	}
	//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};
	int sum = 0;

	F(t, N) if(!vis[t]){
		P("--------------------------------------------");
		H(t);
		int 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]];
			int f1 = cycle[(i-1+c)%c];
			int f2 = cycle[i];
			edgelist[2*N].v = p.u;
			int maxu = -1, maxd = -1;
			P("root: "<<p.u);
			dfs2(2*N, 0, f1, f2, maxu, maxd);
			d[i] = maxd;
			int maxu2 = -1, maxd2 = -1;
			edgelist[2*N].v = maxu;
			P("root2: "<<maxu);
			dfs2(2*N, 0, f1, f2, maxu2, maxd2);
			maxtot = max(maxtot, maxd2);
		}
		H(maxtot);
		P("step 2");

		vector<int> pref(c*2+1, 0);
		F(i, c){
			pref[i+1] = pref[i] + edgelist[cycle[i%c]].w;
		}
		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()-pref[i]+d[i%c]);
			sm.slide(pref[i]+d[i%c]);
		}
		P("step 4");
		H(maxtot);
		sum += maxtot;

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

Subtask #1
18.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Incorrect 3 ms 380 KB Output isn't correct
8 Incorrect 2 ms 376 KB Output isn't correct
9 Incorrect 2 ms 376 KB Output isn't correct
10 Correct 2 ms 376 KB Output is correct
11 Incorrect 2 ms 376 KB Output isn't correct

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 1912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 37 ms 6776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 120 ms 20444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 212 ms 38768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 445 ms 98160 KB Output is correct
2 Incorrect 1354 ms 131072 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 504 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -