oj.uz

Submission #59216

# Submission time Handle Problem Language Result Execution time Memory
59216 2018-07-21T07:20:20 Z gnoor Islands (IOI08_islands) C++17
70 / 100
 1136 ms 132096 KB 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

struct edge {
	int to,wgt;
	int id;
};

vector<edge> pth[1000100];
bool visit[1000100];
bool incyc[1000100];

int cyc[2000100];
long long wgt[2000100];
long long dis[2000100];
int cn;

int dfs(int x,int p) {
	visit[x]=true;
	int ret=0;
	bool toret=false;
	for (auto i:pth[x]) {
		if (i.id==p) continue;
		if (visit[i.to]) {
			if (toret) continue;
			cyc[cn]=x;
			wgt[cn]=i.wgt;
			incyc[x]=true;
			cn++;
			ret=i.to;
			toret=true;
			continue;
		}
		int res=dfs(i.to,i.id);
		if (toret) continue;
		if (res) {
			cyc[cn]=x;
			wgt[cn]=i.wgt;
			incyc[x]=true;
			cn++;
			if (res!=x) ret=res;
			else ret=0;
			toret=true;
		}
	}
	return ret;
}

long long dmax[1000100];
long long survey(int x,int p) {
	long long res=0;
	long long mx=0;
	long long smx=0;
	long long cur;
	dmax[x]=0;
	for (auto i:pth[x]) {
		if (i.id==p) continue;
		if (incyc[i.to]) continue;
		cur=i.wgt+survey(i.to,i.id);
		if (cur>=mx) {
			smx=mx;
			mx=cur;
		} else if (cur>smx) {
			smx=cur;
		}
		res=max(res,cur);
		dmax[x]=max(dmax[x],dmax[i.to]);
	}
	dmax[x]=max(dmax[x],mx+smx);
	return res;
}

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,i});
		pth[a].push_back(edge{i,b,i});
	}
	long long ans=0;
	for (int i=1;i<=n;i++) {
		if (visit[i]) continue;
		cn=1;
		dfs(i,0);
		cn--;
		for (int j=1;j<=cn;j++) {
			dis[j]=survey(cyc[j],0);	
			dis[j+cn]=dis[j];
			wgt[j+cn]=wgt[j];
			cyc[j+cn]=cyc[j];
		}
		wgt[0]=0;
		for (int j=1;j<=cn*2;j++) {
			wgt[j]+=wgt[j-1];
		}	
		deque<int> qq;
		qq.push_back(1);
		long long cur=0;
		for (int j=2;j<=cn*2;j++) {
			while (!qq.empty()&&qq.front()<=j-cn) qq.pop_front();
			cur=max(cur,wgt[j]+dis[j]+dis[qq.front()]-wgt[qq.front()]);
			cur=max(cur,dmax[cyc[j]]);

			while (!qq.empty()&&dis[qq.back()]-wgt[qq.back()]<=dis[j]-wgt[j]) qq.pop_back();
			qq.push_back(j);
		}
		ans+=cur;
	}
	printf("%lld\n",ans);
	return 0;
}

Compilation message

islands.cpp: In function 'int main()':
islands.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
islands.cpp:82: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
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 23928 KB Output is correct
2 Correct 25 ms 23996 KB Output is correct
3 Correct 25 ms 24032 KB Output is correct
4 Correct 25 ms 24036 KB Output is correct
5 Correct 29 ms 24036 KB Output is correct
6 Correct 29 ms 24036 KB Output is correct
7 Correct 26 ms 24036 KB Output is correct
8 Correct 25 ms 24124 KB Output is correct
9 Correct 25 ms 24124 KB Output is correct
10 Correct 24 ms 24132 KB Output is correct
11 Correct 25 ms 24132 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24180 KB Output is correct
2 Correct 26 ms 24192 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24228 KB Output is correct
2 Correct 34 ms 24664 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 25504 KB Output is correct
2 Correct 68 ms 28616 KB Output is correct
3 Correct 50 ms 28616 KB Output is correct
4 Correct 37 ms 28616 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 31008 KB Output is correct
2 Correct 96 ms 34460 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 42288 KB Output is correct
2 Correct 197 ms 50740 KB Output is correct
3 Correct 208 ms 67212 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 67212 KB Output is correct
2 Correct 354 ms 97188 KB Output is correct
3 Correct 392 ms 108440 KB Output is correct
4 Runtime error 538 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 593 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 1136 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 -