oj.uz

답안 #861572

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
861572 2023-10-16T13:38:56 Z hocky 봉쇄 시간 (IOI23_closing) C++17
43 / 100
 77 ms 38484 KB 
#include "closing.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i = a;i < b;i++)
#define trav(nx, v) for(auto &nx : v)
#define all(a) begin(a), end(a)
#define sz(v) (int) v.size()

int n;
typedef array<LL, 4> CostNodeFrom;
CostNodeFrom plain = {-1,-1,-1,-1};
multiset<CostNodeFrom> prim;
const int LIM = 200000;
vector <PLL> edge[LIM + 5];
bool isInside[LIM + 5][2];
LL curans[LIM + 5];
CostNodeFrom cheap[LIM + 5][2];
ostream& operator<<(ostream &os, CostNodeFrom c) {
	os <<"(" << c[0] << ", " << c[1] << ", " << c[2] << ", " << c[3] <<")";
	return os;
}
 

void updateCheap(int node, LL val, bool isY) {
	//~ cout << "Updating " << endl;
	cheap[node][isY] = plain;
	if(cheap[node][!isY][1] != -1) {
		prim.erase(prim.find(cheap[node][!isY]));
		curans[node] += val;
		cheap[node][!isY][0] = max(0LL, cheap[node][!isY][3] - curans[node]);
		prim.insert(cheap[node][!isY]);
	} else {
		curans[node] += val;
	}
}

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W){
	K *= 2;
	n = N;
	rep(i,0,N) {
		edge[i].clear();
		isInside[i][0] = isInside[i][1] = 0;
		curans[i] = 0;
		cheap[i][0] = cheap[i][1] = plain;
	}
	//~ cout << "Here " << U[0] << " " << V[0] << ""  << W[0] << endl;
	prim.clear();
	rep(i,0,N - 1){
		auto tmp = 2LL * W[i];
		if(tmp > K) continue;
		//~ cout << U[i] << " " << V[i] << endl;
		edge[U[i]].emplace_back(V[i], tmp);
		edge[V[i]].emplace_back(U[i], tmp);
		
	}
	isInside[X][0] = 1;
	isInside[Y][1] = 1;
	LL ans = 2;
	trav(tmp, edge[X]){
		CostNodeFrom nx = {tmp.se, tmp.fi, 0, tmp.se};
		prim.insert(nx);
		cheap[tmp.fi][0] = nx;
	}
	trav(tmp, edge[Y]) {
		CostNodeFrom nx = {tmp.se, tmp.fi, 1, tmp.se};
		prim.insert(nx);
		cheap[tmp.fi][1] = nx;
	}
	while(sz(prim)){
		auto currentTop = *prim.begin();
		//~ cout << "here K = " << K << " relaxing node " << currentTop[1] << " with cost " << currentTop[0] << " from node " << currentTop[2] << endl;
		prim.erase(prim.begin());
		if(K < currentTop[0]) break;
		updateCheap(currentTop[1], currentTop[0], currentTop[2]);
		trav(cur, edge[currentTop[1]]){
			if(isInside[cur.fi][currentTop[2]]) continue;
			auto addCost = max(currentTop[3] + cur.se - curans[cur.fi], 0LL);
			CostNodeFrom nxCheap = {addCost, cur.fi, currentTop[2], currentTop[3] + cur.se};
			cheap[cur.fi][currentTop[2]] = nxCheap;
			prim.insert(nxCheap);
		}
		K -= currentTop[0];
		ans++;
		isInside[currentTop[1]][currentTop[2]] = 1;
	}
	//~ rep(i,0,n){
		//~ cout << curans[i] << " ";
	//~ }
	//~ cout << endl;
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 37976 KB Output is correct
2 Correct 77 ms 38484 KB Output is correct
3 Correct 39 ms 12116 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7508 KB Output is correct
2 Correct 1 ms 7004 KB Output is correct
3 Correct 2 ms 7004 KB Output is correct
4 Correct 1 ms 7004 KB Output is correct
5 Correct 2 ms 7004 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 2 ms 7004 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct
9 Correct 1 ms 7004 KB Output is correct
10 Correct 2 ms 7004 KB Output is correct
11 Correct 2 ms 7004 KB Output is correct
12 Correct 2 ms 7000 KB Output is correct
13 Correct 2 ms 7256 KB Output is correct
14 Correct 2 ms 7004 KB Output is correct
15 Correct 2 ms 7004 KB Output is correct
16 Correct 1 ms 7004 KB Output is correct
17 Correct 2 ms 7004 KB Output is correct
18 Correct 2 ms 7004 KB Output is correct
19 Correct 2 ms 7004 KB Output is correct
20 Correct 2 ms 7140 KB Output is correct
21 Correct 2 ms 7200 KB Output is correct
22 Correct 2 ms 7004 KB Output is correct
23 Correct 2 ms 7004 KB Output is correct
24 Correct 2 ms 7004 KB Output is correct
25 Correct 2 ms 7004 KB Output is correct
26 Correct 3 ms 9560 KB Output is correct
27 Correct 3 ms 9564 KB Output is correct
28 Correct 3 ms 9560 KB Output is correct
29 Correct 4 ms 9564 KB Output is correct
30 Correct 2 ms 9308 KB Output is correct
31 Correct 3 ms 9520 KB Output is correct
32 Correct 3 ms 9560 KB Output is correct

Subtask #5
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 7000 KB Output is correct
2 Correct 2 ms 7508 KB Output is correct
3 Correct 1 ms 7004 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 1 ms 7004 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Incorrect 2 ms 7004 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
8 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 7000 KB Output is correct
2 Correct 2 ms 7508 KB Output is correct
3 Correct 1 ms 7004 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 1 ms 7004 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 2 ms 7004 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct
9 Correct 2 ms 7004 KB Output is correct
10 Correct 1 ms 7004 KB Output is correct
11 Correct 2 ms 7004 KB Output is correct
12 Correct 2 ms 7004 KB Output is correct
13 Correct 2 ms 7000 KB Output is correct
14 Correct 2 ms 7256 KB Output is correct
15 Correct 2 ms 7004 KB Output is correct
16 Correct 2 ms 7004 KB Output is correct
17 Correct 1 ms 7004 KB Output is correct
18 Correct 2 ms 7004 KB Output is correct
19 Incorrect 2 ms 7004 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
20 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 7000 KB Output is correct
2 Correct 2 ms 7508 KB Output is correct
3 Correct 1 ms 7004 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 1 ms 7004 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 2 ms 7004 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct
9 Correct 2 ms 7004 KB Output is correct
10 Correct 1 ms 7004 KB Output is correct
11 Correct 2 ms 7004 KB Output is correct
12 Correct 2 ms 7004 KB Output is correct
13 Correct 2 ms 7000 KB Output is correct
14 Correct 2 ms 7256 KB Output is correct
15 Correct 2 ms 7004 KB Output is correct
16 Correct 2 ms 7004 KB Output is correct
17 Correct 1 ms 7004 KB Output is correct
18 Correct 2 ms 7004 KB Output is correct
19 Correct 2 ms 7004 KB Output is correct
20 Correct 2 ms 7004 KB Output is correct
21 Correct 2 ms 7140 KB Output is correct
22 Correct 2 ms 7200 KB Output is correct
23 Correct 2 ms 7004 KB Output is correct
24 Correct 2 ms 7004 KB Output is correct
25 Correct 2 ms 7004 KB Output is correct
26 Incorrect 2 ms 7004 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
27 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 7000 KB Output is correct
2 Correct 2 ms 7508 KB Output is correct
3 Correct 1 ms 7004 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 1 ms 7004 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 2 ms 7004 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct
9 Correct 2 ms 7004 KB Output is correct
10 Correct 1 ms 7004 KB Output is correct
11 Correct 2 ms 7004 KB Output is correct
12 Correct 2 ms 7004 KB Output is correct
13 Correct 2 ms 7000 KB Output is correct
14 Correct 2 ms 7256 KB Output is correct
15 Correct 2 ms 7004 KB Output is correct
16 Correct 2 ms 7004 KB Output is correct
17 Correct 1 ms 7004 KB Output is correct
18 Correct 2 ms 7004 KB Output is correct
19 Correct 2 ms 7004 KB Output is correct
20 Correct 2 ms 7004 KB Output is correct
21 Correct 2 ms 7140 KB Output is correct
22 Correct 2 ms 7200 KB Output is correct
23 Correct 2 ms 7004 KB Output is correct
24 Correct 2 ms 7004 KB Output is correct
25 Correct 2 ms 7004 KB Output is correct
26 Correct 2 ms 7004 KB Output is correct
27 Correct 3 ms 9560 KB Output is correct
28 Correct 3 ms 9564 KB Output is correct
29 Correct 3 ms 9560 KB Output is correct
30 Correct 4 ms 9564 KB Output is correct
31 Correct 2 ms 9308 KB Output is correct
32 Correct 3 ms 9520 KB Output is correct
33 Correct 3 ms 9560 KB Output is correct
34 Incorrect 2 ms 7004 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
35 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 7000 KB Output is correct
2 Correct 2 ms 7508 KB Output is correct
3 Correct 1 ms 7004 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 1 ms 7004 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 2 ms 7004 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct
9 Correct 2 ms 7004 KB Output is correct
10 Correct 1 ms 7004 KB Output is correct
11 Correct 2 ms 7004 KB Output is correct
12 Correct 2 ms 7004 KB Output is correct
13 Correct 2 ms 7000 KB Output is correct
14 Correct 2 ms 7256 KB Output is correct
15 Correct 2 ms 7004 KB Output is correct
16 Correct 2 ms 7004 KB Output is correct
17 Correct 1 ms 7004 KB Output is correct
18 Correct 2 ms 7004 KB Output is correct
19 Correct 2 ms 7004 KB Output is correct
20 Correct 2 ms 7004 KB Output is correct
21 Correct 2 ms 7140 KB Output is correct
22 Correct 2 ms 7200 KB Output is correct
23 Correct 2 ms 7004 KB Output is correct
24 Correct 2 ms 7004 KB Output is correct
25 Correct 2 ms 7004 KB Output is correct
26 Correct 2 ms 7004 KB Output is correct
27 Correct 3 ms 9560 KB Output is correct
28 Correct 3 ms 9564 KB Output is correct
29 Correct 3 ms 9560 KB Output is correct
30 Correct 4 ms 9564 KB Output is correct
31 Correct 2 ms 9308 KB Output is correct
32 Correct 3 ms 9520 KB Output is correct
33 Correct 3 ms 9560 KB Output is correct
34 Incorrect 2 ms 7004 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
35 Halted 0 ms 0 KB -