oj.uz

Submission #57764

# Submission time Handle Problem Language Result Execution time Memory
57764 2018-07-16T03:26:27 Z gnoor Islands (IOI08_islands) C++17
47 / 100
 773 ms 132096 KB 
#include <cstdio>
#include <queue>
#include <cassert>
#include <vector>

using namespace std;

struct edge {
	int to,wgt;
};

vector<edge> pth[1000100];
bool visit[1000100];
long long ans;
vector<int> stk;
vector<int> cycle;
vector<long long> subCost;
vector<long long> cost;

void dfs(int idx,int par) {
	stk.push_back(idx);
	visit[idx]=true;
	int cnt=0;
	for (int i=0;i<(int)pth[idx].size();i++) {
		if (!cnt&&pth[idx][i].to==par) {
			cnt++;
			continue;
		}
		if (visit[pth[idx][i].to]) {
			//printf("ops %d %d\n",idx,pth[idx][i].to);
			//for (int j=0;j<stk.size();j++) {
				//printf("%d ",stk[j]);
			//}	
			//printf("\n");
			if (cycle.size()==0) {
				//printf("change\n");
				for (int j=stk.size()-1;j>=0;j--) {
					cycle.push_back(stk[j]);
					//printf("add %d %d\n",stk[j],pth[idx][i].to);
					if (stk[j]==pth[idx][i].to) break;
				}
			}
			continue;
		}
		dfs(pth[idx][i].to,idx);
	}

	stk.pop_back();
}

long long findCost(int idx,int a,int b) {
	long long ans=0;
	for (int i=0;i<(int)pth[idx].size();i++) {
		if (pth[idx][i].to==a||pth[idx][i].to==b) continue;
		ans=max(ans,findCost(pth[idx][i].to,idx,-1)+pth[idx][i].wgt);	
	}	
	return ans;
}

long long findd(int idx,int val) {
	for (int i=0;i<(int)pth[idx].size();i++) {
		if (pth[idx][i].to==val) return pth[idx][i].wgt;
	}
	assert(0);
}

int main () {
	int n;
	scanf("%d",&n);
	int a,b;
	for (int i=1;i<=n;i++) {
		scanf("%d%d",&a,&b);
		pth[i].push_back(edge{a,b});
		pth[a].push_back(edge{i,b});
	}
	long long ans=0;

	for (int i=1;i<=n;i++) {
		if (visit[i]) continue;
		stk.clear();
		cycle.clear();
		dfs(i,i);
		//printf("+++ %d\n",i);
		subCost.clear();
		cost.clear();
		int nn=cycle.size();

		//for (int j=0;j<nn;j++) {
			//printf("%d ",cycle[j]);
		//}
		//printf("\n");
		for (int j=0;j<nn;j++) {
			long long tmp=findCost(cycle[j],cycle[(j+1)%nn],cycle[(j-1+nn)%nn]);
			subCost.push_back(tmp);
			if (nn!=2) cost.push_back(findd(cycle[j],cycle[(j-1+nn)%nn]));
		}
		if (nn==2) {
			cost.push_back(pth[cycle[0]][0].wgt);
			cost.push_back(pth[cycle[0]][1].wgt);
		}
		//for (int j=0;j<nn;j++) {
			//printf("%lld ",cost[j]);
		//}
		//printf("\n");
		for (int j=0;j<nn;j++) {
			subCost.push_back(subCost[j]);
			cost.push_back(cost[j]);
		}
		//for (int j=0;j<nn*2;j++) {
			//printf("%lld ",cost[j]);
		//}
		//printf("\n");
		cost[0]=0;
		for (int j=1;j<nn*2;j++) {
			cost[j]+=cost[j-1];
		}
		//for (int j=0;j<2*nn;j++) {
			//printf("%d,%lld,%lld ",cycle[j%nn],subCost[j],cost[j]);
		//}
		//printf("\n");
		vector<long long> tbl(nn*2);
		for (int j=0;j<nn*2;j++) {
			tbl[j]=subCost[j];
			tbl[j]-=cost[j];
			//printf("%lld ",tbl[j]);
		}
		//printf("\n");
		deque<int> qq;
		qq.push_back(0);
		long long mx=0;
		for (int j=1;j<nn*2;j++) {
			while (!qq.empty()&&qq.front()<=j-nn) qq.pop_front();
			mx=max(mx,tbl[qq.front()]+cost[j]+subCost[j]);
			//printf ("%lld ",tbl[qq.front()]+cost[j]+subCost[j]);
			while (!qq.empty()&&tbl[qq.back()]<=tbl[j]) qq.pop_back();
			qq.push_back(j);
		}
		//printf("\n");
		ans+=mx;
		//printf("++%lld\n",mx);		
	}
	printf("%lld\n",ans);
	return 0;
}

Compilation message

islands.cpp: In function 'int main()':
islands.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
islands.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1
24.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23804 KB Output is correct
2 Incorrect 20 ms 23980 KB Output isn't correct
3 Correct 21 ms 24056 KB Output is correct
4 Correct 22 ms 24056 KB Output is correct
5 Correct 22 ms 24056 KB Output is correct
6 Correct 24 ms 24056 KB Output is correct
7 Correct 21 ms 24056 KB Output is correct
8 Correct 22 ms 24056 KB Output is correct
9 Incorrect 20 ms 24068 KB Output isn't correct
10 Incorrect 21 ms 24068 KB Output isn't correct
11 Correct 21 ms 24076 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24208 KB Output is correct
2 Correct 22 ms 24208 KB Output is correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 24240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 25164 KB Output is correct
2 Correct 79 ms 28384 KB Output is correct
3 Correct 51 ms 28384 KB Output is correct
4 Incorrect 38 ms 28384 KB Output isn't correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 30660 KB Output is correct
2 Correct 97 ms 33320 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 39972 KB Output is correct
2 Correct 253 ms 50184 KB Output is correct
3 Correct 277 ms 65744 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 65744 KB Output is correct
2 Correct 384 ms 92576 KB Output is correct
3 Correct 408 ms 107176 KB Output is correct
4 Runtime error 511 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 427 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 773 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -