Submission #20414

#	Time	Username	Problem	Language	Result	Execution time	Memory
20414		tlwpdus (#35)	Can polan into space? (OJUZ11_space)	C++98	100 / 100	183 ms	22988 KiB

space

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
 
using namespace std;
 
typedef long long ll;

int n;
ll str[200100][3];
ll dyn[200100][2];
int via[200100][2];
vector<int> lis[200100];
int deg[200100];
queue<int> q;

int main() {
	int i, j;
	scanf("%d",&n);
	for (i=0;i<n;i++) {
		for (j=0;j<3;j++) scanf("%d",&str[i][j]);
	}
	dyn[0][0] = str[0][0];
	dyn[0][1] = str[0][1];
	for (i=1;i<n;i++) {
		if (dyn[i-1][0]+str[i][1]<dyn[i-1][1]+str[i][0]) dyn[i][0] = dyn[i-1][1]+str[i][0], via[i][0] = 1;
		else dyn[i][0] = dyn[i-1][0]+str[i][1], via[i][0] = 0;
		if (i==n-1) continue;
		if (dyn[i-1][0]+str[i][2]<dyn[i-1][1]+str[i][1]) dyn[i][1] = dyn[i-1][1]+str[i][1], via[i][1] = 1;
		else dyn[i][1] = dyn[i-1][0]+str[i][2], via[i][1] = 0;
	}
	int p = 0;
	for (i=n-1;i>0;i--) {
		p = via[i][p];
		if (p) {lis[i].push_back(i-1),deg[i-1]++;}
		else {lis[i-1].push_back(i),deg[i]++;}
	}
	for (i=0;i<n;i++) if (!deg[i]) q.push(i);
	printf("%lld\n",dyn[n-1][0]);
	while(!q.empty()) {
		int here = q.front();
		q.pop();
		printf("%d ",here+1);
		for (i=0;i<lis[here].size();i++) {
			int there = lis[here][i];
			deg[there]--;
			if (!deg[there]) q.push(there);
		}
	}
	printf("\n");

	return 0;
}

Compilation message (stderr)

space.cpp: In function 'int main()':
space.cpp:23:42: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
   for (j=0;j<3;j++) scanf("%d",&str[i][j]);
                                          ^
space.cpp:46:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (i=0;i<lis[here].size();i++) {
             ^
space.cpp:21:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
space.cpp:23:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (j=0;j<3;j++) scanf("%d",&str[i][j]);
                                           ^

• Subtask 1: 11 / 11
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 26 / 26
• Subtask 5: 28 / 28