oj.uz

답안 #939343

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
939343 2024-03-06T09:35:26 Z WanWan 봉쇄 시간 (IOI23_closing) C++17
51 / 100
 1000 ms 10068 KB 
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
#define int long long
const int MAXN = 3005;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9+7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 
vector<pi>adj[MAXN];

int par[MAXN];
int dep[MAXN];

void dfs(int x, int p){
   	par[x]=p;
   	for(auto v:adj[x])if(v.first!=p){
   		dep[v.first]=dep[x]+1;
   		dfs(v.first,x);
   	}
}
int dd[2][MAXN];
void bfs(int src, int xx){
	queue<int> qu;
	memset(dd[xx],-1,sizeof dd[xx]);
	dd[xx][src]=0;
	qu.push(src);
	while(qu.size()){
		int c=qu.front();
		qu.pop();

		for(auto v:adj[c]){
			if(dd[xx][v.first] == -1 || dd[xx][v.first] > dd[xx][c]+v.second){
				dd[xx][v.first]=dd[xx][c]+v.second;
				qu.push(v.first);
			}
		}
	}
}
map<int,int>cst;
int32_t max_score(int32_t n, int32_t X, int32_t Y, long long K,
              std::vector<int32_t> U, std::vector<int32_t> V, std::vector<int32_t> W)
{
	for(int i=0;i<n;i++){
		adj[i].clear();
	}
    for(int i=0;i<n-1;i++){
        adj[U[i]].push_back({V[i],W[i]});
        adj[V[i]].push_back({U[i],W[i]});
    }
   	dfs(1,-1);
   	vector<int> v1,v2;
   	int x=X,y=Y;
   	while(x!=y){
   		if(dep[x]>dep[y]){
   			v1.push_back(x);
   			x=par[x];
   		} else{
   			v2.push_back(y);
   			y=par[y];
   		}
   	}

   	unordered_set<int> path;
   	reverse(v2.begin(),v2.end());
   	vector<int> vec;
   	for(auto e:v1)vec.push_back(e);
   	vec.push_back(x);
   	for(auto e:v2)vec.push_back(e);
   	for(auto e:vec)path.insert(e);
	int ans=2;
   	// 1. calc if there's 0 intersection--just greedily choose the cheapest node
	bfs(X,0);
	bfs(Y,1);

	{
		vector<int> vs;
		for(int i=0;i<n;i++)vs.push_back(dd[0][i]);
		for(int i=0;i<n;i++)vs.push_back(dd[1][i]);
		sort(vs.begin(),vs.end());
		int cst=0;
		int cc=0;
		for(auto x:vs){
			cst+=x;
			++cc;
			if(cst<=K){
				ans=max(ans,cc);
			} else{
				break;
			}
		}
	}
	priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> one; //{cost,index,min/max}
   	priority_queue<pi,vector<pi>,greater<pi>> both;
   	// 2. if there's at least 1 intersection, it'll happen on the path
   
   	for(int k=0;k<n;k++){
   	if(path.find(k) != path.end()){		
   		} else{
   			both.push({max(dd[0][k],dd[1][k]),k});
			one.push({min(dd[0][k],dd[1][k]),k,0});
   		}
   	}
   			
   	set<pi>doneone;
   	set<int>doneboth;
   	int cost=0;
   	int cnt=0;

   	while(true){
   		
   		// try taking 1 only
   		//cst[cost]=cnt;
   		while(one.size() && doneone.find({one.top()[1],one.top()[2]}) != doneone.end())one.pop();
   		if(one.size()){
   			cst[cnt+1]=cost+one.top()[0];
   			cst[cnt+1]=min(cst[cnt+1],oo);
   			//if(cost+one.top()[0]<=K)ans=max(ans,cnt+1);
   		}

   		int c1=oo,c2=oo;

   		if(one.size()){

   			c1=0;
			array<int,3> cur=one.top();
			c1+=cur[0];

   			one.pop();
   			while(one.size() && doneone.find({one.top()[1],one.top()[2]}) != doneone.end())one.pop();
   			if(one.size())c1+=one.top()[0];
   			else c1=oo;
   			one.push(cur);
   		}
   		while(both.size() && doneboth.find(both.top().second) != doneboth.end())both.pop();
   		if(both.size()){
   			c2=both.top().first;
   		}
   		if(c2==oo && c1==oo)break;

   		if(c2<c1){ // we should take the smaller one of the both
   			assert(both.size());
   			pi cur=both.top();
   			cnt++;
   			cost += min(dd[0][cur.second],dd[1][cur.second]);
   			one.push({abs(dd[0][cur.second]-dd[1][cur.second]),cur.second,1});
   			doneone.insert({cur.second,0});
   			both.pop();
   		} else{

   			array<int,3>cur=one.top();
   			one.pop();
   			cnt++;
   			cost+=cur[0];
   			if(cur[2] == 0){ // push max
   				one.push({max(dd[0][cur[1]],dd[1][cur[1]])-cur[0],cur[1],1});
   				doneboth.insert(cur[1]);
   			}
   		}
   		if(cst.find(cnt) == cst.end())cst[cnt]=cost;
   		else cst[cnt]=min(cst[cnt],cost);
   		cst[cnt]=min(cst[cnt],oo);
   	}
   	for(auto x:cst){
   		debug(x.first,x.second);
   	}


   	for(int i=0;i<vec.size();i++){

   		for(int j=i;j<vec.size();j++){

   			int cost = 0;
   			int cnt=0;
   			
   			for(int k=0;k<vec.size();k++){
   				if(k<i){
   					cost+=min(dd[1][vec[k]],dd[0][vec[k]]);
   					++cnt;
   				}
   				else if(k<=j){
   					cost+=max(dd[0][vec[k]],dd[1][vec[k]]);
   					cnt+=2;
   				}
   				else {
   					cost+=min(dd[1][vec[k]],dd[0][vec[k]]);
   					++cnt;
   				}
   			}

   			if(cost>K)continue;
   			ans=max(ans,cnt);
   			for(auto x:cst){
   				if(cost+x.second<=K){
   					ans=max(ans,cnt+x.first);
   				}
   			}
   		}
   			


   	}
   	cst.clear();
   	return ans;
}

Compilation message

closing.cpp: In function 'int32_t max_score(int32_t, int32_t, int32_t, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:173:14: warning: variable 'x' set but not used [-Wunused-but-set-variable]
  173 |     for(auto x:cst){
      |              ^
closing.cpp:178:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |     for(int i=0;i<vec.size();i++){
      |                 ~^~~~~~~~~~~
closing.cpp:180:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |      for(int j=i;j<vec.size();j++){
      |                  ~^~~~~~~~~~~
closing.cpp:185:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |       for(int k=0;k<vec.size();k++){
      |                   ~^~~~~~~~~~~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #1
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 48 ms 10068 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 604 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 87 ms 668 KB Output is correct
22 Correct 7 ms 600 KB Output is correct
23 Correct 73 ms 800 KB Output is correct
24 Correct 71 ms 600 KB Output is correct

Subtask #4
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 604 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 87 ms 668 KB Output is correct
22 Correct 7 ms 600 KB Output is correct
23 Correct 73 ms 800 KB Output is correct
24 Correct 71 ms 600 KB Output is correct
25 Correct 6 ms 604 KB Output is correct
26 Correct 6 ms 1532 KB Output is correct
27 Correct 6 ms 1372 KB Output is correct
28 Execution timed out 1080 ms 1108 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 604 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 1 ms 344 KB Output is correct
37 Correct 0 ms 344 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 1 ms 604 KB Output is correct
40 Correct 1 ms 604 KB Output is correct
41 Correct 1 ms 600 KB Output is correct
42 Correct 1 ms 604 KB Output is correct
43 Correct 1 ms 348 KB Output is correct
44 Correct 1 ms 348 KB Output is correct
45 Correct 1 ms 604 KB Output is correct
46 Correct 1 ms 604 KB Output is correct
47 Correct 1 ms 420 KB Output is correct
48 Correct 1 ms 604 KB Output is correct
49 Correct 1 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 604 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 87 ms 668 KB Output is correct
23 Correct 7 ms 600 KB Output is correct
24 Correct 73 ms 800 KB Output is correct
25 Correct 71 ms 600 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 0 ms 344 KB Output is correct
43 Correct 1 ms 344 KB Output is correct
44 Correct 0 ms 344 KB Output is correct
45 Correct 1 ms 348 KB Output is correct
46 Correct 1 ms 604 KB Output is correct
47 Correct 1 ms 604 KB Output is correct
48 Correct 1 ms 600 KB Output is correct
49 Correct 1 ms 604 KB Output is correct
50 Correct 1 ms 348 KB Output is correct
51 Correct 1 ms 348 KB Output is correct
52 Correct 1 ms 604 KB Output is correct
53 Correct 1 ms 604 KB Output is correct
54 Correct 1 ms 420 KB Output is correct
55 Correct 1 ms 604 KB Output is correct
56 Correct 1 ms 348 KB Output is correct
57 Correct 0 ms 348 KB Output is correct
58 Correct 1 ms 600 KB Output is correct
59 Correct 1 ms 604 KB Output is correct
60 Correct 3 ms 604 KB Output is correct
61 Correct 2 ms 604 KB Output is correct
62 Correct 2 ms 604 KB Output is correct
63 Correct 2 ms 600 KB Output is correct
64 Correct 2 ms 604 KB Output is correct
65 Correct 5 ms 528 KB Output is correct
66 Correct 1 ms 604 KB Output is correct
67 Correct 1 ms 520 KB Output is correct
68 Correct 46 ms 852 KB Output is correct
69 Correct 98 ms 604 KB Output is correct
70 Correct 2 ms 604 KB Output is correct
71 Correct 4 ms 524 KB Output is correct
72 Correct 2 ms 600 KB Output is correct
73 Correct 1 ms 604 KB Output is correct
74 Correct 2 ms 604 KB Output is correct
75 Correct 1 ms 604 KB Output is correct

Subtask #8
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 604 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 87 ms 668 KB Output is correct
23 Correct 7 ms 600 KB Output is correct
24 Correct 73 ms 800 KB Output is correct
25 Correct 71 ms 600 KB Output is correct
26 Correct 6 ms 604 KB Output is correct
27 Correct 6 ms 1532 KB Output is correct
28 Correct 6 ms 1372 KB Output is correct
29 Execution timed out 1080 ms 1108 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 604 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 87 ms 668 KB Output is correct
23 Correct 7 ms 600 KB Output is correct
24 Correct 73 ms 800 KB Output is correct
25 Correct 71 ms 600 KB Output is correct
26 Correct 6 ms 604 KB Output is correct
27 Correct 6 ms 1532 KB Output is correct
28 Correct 6 ms 1372 KB Output is correct
29 Execution timed out 1080 ms 1108 KB Time limit exceeded
30 Halted 0 ms 0 KB -