oj.uz

Submission #849048

# Submission time Handle Problem Language Result Execution time Memory
849048 2023-09-14T02:43:21 Z Lib Closing Time (IOI23_closing) C++17
43 / 100
 140 ms 45096 KB 
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
struct edge{
	int first;
	long long second;
	int previ;
};
vector <vector<edge> > adj;
long long check[200003];
long long Cost1[200003];
long long Cost2[200003];
long long DistX[200003];
long long DistY[200003];
long long BFSCheck[200003];
long long CPrev[200003];
long long N,X,Y,K,n;
long long ans1,ans2;
vector <int> XYPath;
int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
	int n=N;
	int x=X;
	int y=Y;
	long long k=K;
	long long len;
	long long Budget;
	long long tans;
	int s,e;
	vector <edge> vtemp;
	priority_queue <pair <long long,int> > pq;
	vector <int> clist;
	int cur;
	int cur2;
	adj.clear();
		n=N;
		XYPath.clear();
		while(!pq.empty()){
			pq.pop();
		}
		for(int i=0;i<=n+1;i++){
			adj.push_back(vtemp);
			check[i]=0;
			Cost1[i]=0;
			Cost2[i]=0;
			DistX[i]=0;
			DistY[i]=0;
		}
		ans1=0;
		ans2=0;
		for(int i=0;i<n-1;i++){
			s=U[i];
			e=V[i];
			len=W[i];
			adj[s].push_back({e,len});
			adj[e].push_back({s,len});
		}
		//BFS tu X
		for(int i=0;i<n;i++){
			CPrev[i]=-1;
			BFSCheck[i]=0;
		}
		cur=0;
		clist.clear();
		clist.push_back(X);
		DistX[X]=0;
		BFSCheck[X]=1;
		while(cur<clist.size()){
			for(int i=0;i<adj[clist[cur]].size();i++){
				if(BFSCheck[adj[clist[cur]][i].first]==0){
					BFSCheck[adj[clist[cur]][i].first]=1;
					DistX[adj[clist[cur]][i].first]=DistX[clist[cur]]+adj[clist[cur]][i].second;
					clist.push_back(adj[clist[cur]][i].first);
					CPrev[adj[clist[cur]][i].first]=clist[cur];
				}
			}
			//Tim duong di tu X den Y
			if(clist[cur]==Y){
				cur2=Y;
				while(CPrev[cur2]!=-1){
					XYPath.push_back(cur2);
					cur2=CPrev[cur2];
				}
				XYPath.push_back(X);
			}
			cur++;
		}
		//BFS tu Y
		for(int i=0;i<n;i++){
			check[i]=0;
			BFSCheck[i]=0;
		}
		cur=0;
		clist.clear();
		clist.push_back(Y);
		DistY[Y]=0;
		BFSCheck[Y]=1;
		while(cur<clist.size()){
			for(int i=0;i<adj[clist[cur]].size();i++){
				if(BFSCheck[adj[clist[cur]][i].first]==0){
					BFSCheck[adj[clist[cur]][i].first]=1;
					DistY[adj[clist[cur]][i].first]=DistY[clist[cur]]+adj[clist[cur]][i].second;
					clist.push_back(adj[clist[cur]][i].first);
					CPrev[adj[clist[cur]][i].first]=clist[cur];
				}
			}
			cur++;
		}
		//initialize 2 mang Cost1 va Cost2
		for(int i=0;i<n;i++){
			Cost1[i]=min(DistX[i],DistY[i]);
			Cost2[i]=max(DistX[i],DistY[i])-Cost1[i];
		}
		//Case 1: Chi nang cap cac dinh len loai 1
		for(int i=0;i<n;i++){
			pq.push({-Cost1[i],0});
		}
		Budget=K;
		ans1=0;
		while(Budget>=0&&!pq.empty()){
			Budget+=pq.top().first;
			ans1++;
			pq.pop();
		}
		if(Budget<0){
			ans1--;
		}
		//Case2: Ton tai it nhat 1 dinh duoc nang cap len loai 2
		while(!pq.empty()){
			pq.pop();
		}
		tans=ans1;
		Budget=K;
		ans2=0;
		for(int i=0;i<n;i++){
			check[i]=0;
		}
		for(int i=0;i<XYPath.size();i++){
			Budget-=Cost1[XYPath[i]];
			check[XYPath[i]]=1;
			ans2++;
		}
		if(Budget>0){
			for(int i=0;i<n;i++){
				if(check[i]==0){
					pq.push({-Cost1[i],i});
				}else{
					pq.push({-Cost2[i],i});
				}
			}
			while(!pq.empty()&&Budget>0){
				Budget+=pq.top().first;
				if(Budget>=0){
				ans2++;
				cur=pq.top().second;
				pq.pop();
				check[cur]++;
				if(check[cur]==1){
					pq.push({-Cost2[cur],cur});
				}
				}
			}
			tans=max(ans1,ans2);
		}
	return tans;
}

Compilation message

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:68:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   while(cur<clist.size()){
      |         ~~~^~~~~~~~~~~~~
closing.cpp:69:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |    for(int i=0;i<adj[clist[cur]].size();i++){
      |                ~^~~~~~~~~~~~~~~~~~~~~~~
closing.cpp:98:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |   while(cur<clist.size()){
      |         ~~~^~~~~~~~~~~~~
closing.cpp:99:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |    for(int i=0;i<adj[clist[cur]].size();i++){
      |                ~^~~~~~~~~~~~~~~~~~~~~~~
closing.cpp:138:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |   for(int i=0;i<XYPath.size();i++){
      |               ~^~~~~~~~~~~~~~
closing.cpp:23:6: warning: unused variable 'x' [-Wunused-variable]
   23 |  int x=X;
      |      ^
closing.cpp:24:6: warning: unused variable 'y' [-Wunused-variable]
   24 |  int y=Y;
      |      ^
closing.cpp:25:12: warning: unused variable 'k' [-Wunused-variable]
   25 |  long long k=K;
      |            ^

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 44312 KB Output is correct
2 Correct 140 ms 45096 KB Output is correct
3 Correct 79 ms 14672 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10584 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 1 ms 10584 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 2 ms 10584 KB Output is correct
10 Correct 1 ms 10584 KB Output is correct
11 Correct 2 ms 10584 KB Output is correct
12 Correct 2 ms 10584 KB Output is correct
13 Correct 2 ms 10584 KB Output is correct
14 Correct 2 ms 10584 KB Output is correct
15 Correct 2 ms 10584 KB Output is correct
16 Correct 1 ms 10584 KB Output is correct
17 Correct 2 ms 10584 KB Output is correct
18 Correct 2 ms 10584 KB Output is correct
19 Correct 2 ms 10588 KB Output is correct
20 Correct 2 ms 10584 KB Output is correct
21 Correct 2 ms 10588 KB Output is correct
22 Correct 1 ms 10584 KB Output is correct
23 Correct 2 ms 10840 KB Output is correct
24 Correct 2 ms 10584 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10584 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 1 ms 10584 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 2 ms 10584 KB Output is correct
10 Correct 1 ms 10584 KB Output is correct
11 Correct 2 ms 10584 KB Output is correct
12 Correct 2 ms 10584 KB Output is correct
13 Correct 2 ms 10584 KB Output is correct
14 Correct 2 ms 10584 KB Output is correct
15 Correct 2 ms 10584 KB Output is correct
16 Correct 1 ms 10584 KB Output is correct
17 Correct 2 ms 10584 KB Output is correct
18 Correct 2 ms 10584 KB Output is correct
19 Correct 2 ms 10588 KB Output is correct
20 Correct 2 ms 10584 KB Output is correct
21 Correct 2 ms 10588 KB Output is correct
22 Correct 1 ms 10584 KB Output is correct
23 Correct 2 ms 10840 KB Output is correct
24 Correct 2 ms 10584 KB Output is correct
25 Correct 3 ms 10584 KB Output is correct
26 Correct 3 ms 11096 KB Output is correct
27 Correct 3 ms 11096 KB Output is correct
28 Correct 3 ms 11096 KB Output is correct
29 Correct 3 ms 11096 KB Output is correct
30 Correct 3 ms 11096 KB Output is correct
31 Correct 4 ms 11096 KB Output is correct
32 Correct 3 ms 11096 KB Output is correct

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10584 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 1 ms 10584 KB Output is correct
7 Correct 1 ms 10584 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Incorrect 1 ms 10584 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
10 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10584 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 1 ms 10584 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 1 ms 10588 KB Output is correct
10 Correct 2 ms 10584 KB Output is correct
11 Correct 1 ms 10584 KB Output is correct
12 Correct 2 ms 10584 KB Output is correct
13 Correct 2 ms 10584 KB Output is correct
14 Correct 2 ms 10584 KB Output is correct
15 Correct 2 ms 10584 KB Output is correct
16 Correct 2 ms 10584 KB Output is correct
17 Correct 1 ms 10584 KB Output is correct
18 Correct 2 ms 10584 KB Output is correct
19 Correct 1 ms 10584 KB Output is correct
20 Correct 2 ms 10584 KB Output is correct
21 Incorrect 1 ms 10584 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
22 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10584 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 1 ms 10584 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 1 ms 10588 KB Output is correct
10 Correct 2 ms 10584 KB Output is correct
11 Correct 1 ms 10584 KB Output is correct
12 Correct 2 ms 10584 KB Output is correct
13 Correct 2 ms 10584 KB Output is correct
14 Correct 2 ms 10584 KB Output is correct
15 Correct 2 ms 10584 KB Output is correct
16 Correct 2 ms 10584 KB Output is correct
17 Correct 1 ms 10584 KB Output is correct
18 Correct 2 ms 10584 KB Output is correct
19 Correct 2 ms 10584 KB Output is correct
20 Correct 2 ms 10588 KB Output is correct
21 Correct 2 ms 10584 KB Output is correct
22 Correct 2 ms 10588 KB Output is correct
23 Correct 1 ms 10584 KB Output is correct
24 Correct 2 ms 10840 KB Output is correct
25 Correct 2 ms 10584 KB Output is correct
26 Correct 1 ms 10584 KB Output is correct
27 Correct 2 ms 10584 KB Output is correct
28 Incorrect 1 ms 10584 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
29 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10584 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 1 ms 10584 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 1 ms 10588 KB Output is correct
10 Correct 2 ms 10584 KB Output is correct
11 Correct 1 ms 10584 KB Output is correct
12 Correct 2 ms 10584 KB Output is correct
13 Correct 2 ms 10584 KB Output is correct
14 Correct 2 ms 10584 KB Output is correct
15 Correct 2 ms 10584 KB Output is correct
16 Correct 2 ms 10584 KB Output is correct
17 Correct 1 ms 10584 KB Output is correct
18 Correct 2 ms 10584 KB Output is correct
19 Correct 2 ms 10584 KB Output is correct
20 Correct 2 ms 10588 KB Output is correct
21 Correct 2 ms 10584 KB Output is correct
22 Correct 2 ms 10588 KB Output is correct
23 Correct 1 ms 10584 KB Output is correct
24 Correct 2 ms 10840 KB Output is correct
25 Correct 2 ms 10584 KB Output is correct
26 Correct 3 ms 10584 KB Output is correct
27 Correct 3 ms 11096 KB Output is correct
28 Correct 3 ms 11096 KB Output is correct
29 Correct 3 ms 11096 KB Output is correct
30 Correct 3 ms 11096 KB Output is correct
31 Correct 3 ms 11096 KB Output is correct
32 Correct 4 ms 11096 KB Output is correct
33 Correct 3 ms 11096 KB Output is correct
34 Correct 1 ms 10584 KB Output is correct
35 Correct 2 ms 10584 KB Output is correct
36 Incorrect 1 ms 10584 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
37 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10584 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 1 ms 10584 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 1 ms 10588 KB Output is correct
10 Correct 2 ms 10584 KB Output is correct
11 Correct 1 ms 10584 KB Output is correct
12 Correct 2 ms 10584 KB Output is correct
13 Correct 2 ms 10584 KB Output is correct
14 Correct 2 ms 10584 KB Output is correct
15 Correct 2 ms 10584 KB Output is correct
16 Correct 2 ms 10584 KB Output is correct
17 Correct 1 ms 10584 KB Output is correct
18 Correct 2 ms 10584 KB Output is correct
19 Correct 2 ms 10584 KB Output is correct
20 Correct 2 ms 10588 KB Output is correct
21 Correct 2 ms 10584 KB Output is correct
22 Correct 2 ms 10588 KB Output is correct
23 Correct 1 ms 10584 KB Output is correct
24 Correct 2 ms 10840 KB Output is correct
25 Correct 2 ms 10584 KB Output is correct
26 Correct 3 ms 10584 KB Output is correct
27 Correct 3 ms 11096 KB Output is correct
28 Correct 3 ms 11096 KB Output is correct
29 Correct 3 ms 11096 KB Output is correct
30 Correct 3 ms 11096 KB Output is correct
31 Correct 3 ms 11096 KB Output is correct
32 Correct 4 ms 11096 KB Output is correct
33 Correct 3 ms 11096 KB Output is correct
34 Correct 1 ms 10584 KB Output is correct
35 Correct 2 ms 10584 KB Output is correct
36 Incorrect 1 ms 10584 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
37 Halted 0 ms 0 KB -