oj.uz

답안 #680938

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
680938 2023-01-12T05:30:24 Z HaiHoang Relay Marathon (NOI20_relaymarathon) C++17
30 / 100
 4278 ms 72120 KB 
/**
*   NAME : PHAM VAN SAM
*   DATE : 12.01.2023 08:03:57
*  ┌───┐   ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐
*  │Esc│   │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S L│P/B│  ┌┐    ┌┐    ┌┐
*  └───┘   └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘  └┘    └┘    └┘
*  ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
*  │~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │Num│ / │ * │ - │
*  ├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤
*  │ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ | \ │ │Del│End│PDn│ │ 7 │ 8 │ 9 │   │
*  ├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │
*  │ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│" '│ Enter  │               │ 4 │ 5 │ 6 │   │
*  ├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤     ┌───┐     ├───┼───┼───┼───┤
*  │ Shift  │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│  Shift   │     │ ↑ │     │ 1 │ 2 │ 3 │   │
*  ├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
*  │ Ctrl│ Win│ Alt│         Space         │ Alt│ Win│Menu│Ctrl│ │ ← │ ↓ │ → │ │   0   │ . │←─┘│
*  └─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
**/
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define MASK(x) (1LL << (x))
#define BIT(x, k) (((x) >> (k)) & 1LL)
#define all(x) (x).begin(),(x).end()
#define For(i, a, b) for (int i = (a); i <= (b); ++i)
#define Fod(i, a, b) for (int i = (a); i >= (b); --i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define Fore(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define file(TASK) if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); }

template <class U, class V> bool maximize(U &A, const V &B){ return (A < B) ? (A = B, true) : false;}
template <class U, class V> bool minimize(U &A, const V &B){ return (A > B) ? (A = B, true) : false;}

using namespace std;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) { return l + rnd() % (r - l + 1); }
const int MAXN = 1e5 + 5;
int N, M, K, d[MAXN];
vector <pair <int, int>> ke[MAXN];
vector <int> special;
namespace sub1 {
	int dp[55][55];
	void dijkstra (int u) {
		priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> heap;
		fill(dp[u] + 1, dp[u] + N + 1, 2e9);
		dp[u][u] = 0;
		heap.push(make_pair(dp[u][u], u));
		while(heap.size()) {
			int x = heap.top().second;
			int w1 = heap.top().first;
			heap.pop();
			if(dp[u][x] != w1) continue;
			for (auto [v, w] : ke[x]) if(minimize(dp[u][v], dp[u][x] + w)) {
				heap.push(make_pair(dp[u][v], v));
			}
		}
	}
	void Main() {
		int ans = 2e9;
		for (auto u : special) dijkstra(u);
		rep (i, (int) special.size()) {
			rep (j, (int) special.size()) {
				For (u, i + 1, (int) special.size() - 1) {
					if(dp[special[i]][special[u]] == 2e9) continue;
					For (v, j + 1, (int) special.size() - 1){
						if(dp[special[j]][special[v]] == 2e9) continue;
						if(i != v && i != j && u != j && u != v) {
							minimize(ans, dp[special[i]][special[u]] + dp[special[j]][special[v]]);
						}
					}
				}
			}
		}
		cout << ans << '\n';
	}
}
namespace LieuAnNhieu{
	int trace[MAXN];
	struct Data {
		int u, v, w;
		Data(int u, int v, int w) {
			this-> u = u;
			this-> v = v;
			this-> w = w;
		}
		friend bool operator < (const Data &A, const Data &B) {
			return (A.w < B.w || (A.w == B.w && A.u < B.u));
		}
		friend bool operator == (const Data &A, const Data &B) {
			return (A.w == B.w && A.u == B.u && A.v == B.v);
		}
	};
	vector <Data> val;
	void dijkstra(int bit, int type) {
		fill(d + 1, d + N + 1, 1e9);
		priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> heap;
		for (auto x : special) if(BIT(x, bit) == type) {
			d[x] = 0;
			trace[x] = x;
			heap.push(make_pair(0, x));
		}
		while(heap.size()) {
			int u = heap.top().second;
			int w1 = heap.top().first;
			heap.pop();
			if(d[u] != w1) continue;
			for (auto [v, w] : ke[u]) if(minimize(d[v], d[u] + w)) {
				heap.push(make_pair(d[v], v));
				trace[v] = trace[u];
			}
		}
		for (auto x : special) {
			if(BIT(x, bit) == type || d[x] == 1e9) continue;
			val.push_back(Data(min(x, trace[x]), max(x, trace[x]), d[x]));
		}
		sort (val.begin(), val.end());
		val.erase(unique(val.begin(), val.end()), val.end());
		while(val.size() > K) val.pop_back();
	}
	void lieu_thi_an_nhieu() {
		For (i, 0, 16) {
			dijkstra(i, 0);
			dijkstra(i, 1);
		}
		int ans = 2e9;
		For (i, 1, (int) val.size()) {
			if(val[0].u != val[i].u && val[0].u != val[i].v && 
			   val[0].v != val[i].u && val[0].v != val[i].v) {
				ans = val[0].w + val[i].w;
			break;
			}
			
		}
		cout << ans << '\n';
	}
}
void solve(void) {
    cin >> N >> M >> K;
    while(M--) {
    	int u, v, w; cin >> u >> v >> w;
    	ke[u].push_back(make_pair(v, w));
    	ke[v].push_back(make_pair(u, w));
    }
    For (i, 1, K) {
    	int x; cin >> x; special.push_back(x);
    }
    if(N <= 50) sub1::Main();
    else LieuAnNhieu::lieu_thi_an_nhieu();
}
signed main() {
    file("4SPECIAL");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int test; test = 1; 
    // cin >> test;
    while(test--) { 
        solve();
        cout << '\n';
    }
    // cerr << "Time elapsed: " << TIME << " s.\n";
    return (0 ^ 0);
}

Compilation message

RelayMarathon.cpp: In function 'void LieuAnNhieu::dijkstra(int, int)':
RelayMarathon.cpp:120:20: warning: comparison of integer expressions of different signedness: 'std::vector<LieuAnNhieu::Data>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  120 |   while(val.size() > K) val.pop_back();
      |         ~~~~~~~~~~~^~~
RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:30:56: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 | #define file(TASK) if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); }
      |                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.cpp:153:5: note: in expansion of macro 'file'
  153 |     file("4SPECIAL");
      |     ^~~~
RelayMarathon.cpp:30:89: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 | #define file(TASK) if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); }
      |                                                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.cpp:153:5: note: in expansion of macro 'file'
  153 |     file("4SPECIAL");
      |     ^~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2696 KB Output is correct
3 Correct 2 ms 2692 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 3 ms 2696 KB Output is correct
8 Correct 2 ms 2744 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 5 ms 2644 KB Output is correct
12 Correct 4 ms 2688 KB Output is correct
13 Correct 4 ms 2664 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct
15 Correct 6 ms 2748 KB Output is correct
16 Correct 2 ms 2684 KB Output is correct
17 Correct 5 ms 2648 KB Output is correct
18 Correct 2 ms 2692 KB Output is correct
19 Correct 5 ms 2644 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 4 ms 2688 KB Output is correct
22 Correct 2 ms 2684 KB Output is correct
23 Correct 4 ms 2644 KB Output is correct
24 Correct 2 ms 2644 KB Output is correct
25 Correct 2 ms 2684 KB Output is correct
26 Correct 2 ms 2644 KB Output is correct
27 Correct 2 ms 2644 KB Output is correct
28 Correct 5 ms 2692 KB Output is correct
29 Correct 3 ms 2696 KB Output is correct
30 Correct 3 ms 2644 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2696 KB Output is correct
3 Correct 2 ms 2692 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 3 ms 2696 KB Output is correct
8 Correct 2 ms 2744 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 5 ms 2644 KB Output is correct
12 Correct 4 ms 2688 KB Output is correct
13 Correct 4 ms 2664 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct
15 Correct 6 ms 2748 KB Output is correct
16 Correct 2 ms 2684 KB Output is correct
17 Correct 5 ms 2648 KB Output is correct
18 Correct 2 ms 2692 KB Output is correct
19 Correct 5 ms 2644 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 4 ms 2688 KB Output is correct
22 Correct 2 ms 2684 KB Output is correct
23 Correct 4 ms 2644 KB Output is correct
24 Correct 2 ms 2644 KB Output is correct
25 Correct 2 ms 2684 KB Output is correct
26 Correct 2 ms 2644 KB Output is correct
27 Correct 2 ms 2644 KB Output is correct
28 Correct 5 ms 2692 KB Output is correct
29 Correct 3 ms 2696 KB Output is correct
30 Correct 3 ms 2644 KB Output is correct
31 Incorrect 3 ms 2644 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 375 ms 6612 KB Output is correct
2 Correct 7 ms 3668 KB Output is correct
3 Correct 3934 ms 67776 KB Output is correct
4 Correct 2815 ms 35900 KB Output is correct
5 Correct 1159 ms 10212 KB Output is correct
6 Correct 966 ms 8924 KB Output is correct
7 Correct 1263 ms 10892 KB Output is correct
8 Correct 402 ms 6604 KB Output is correct
9 Correct 936 ms 8372 KB Output is correct
10 Correct 565 ms 7152 KB Output is correct
11 Correct 4074 ms 70288 KB Output is correct
12 Correct 657 ms 7396 KB Output is correct
13 Correct 2273 ms 24508 KB Output is correct
14 Correct 1225 ms 11340 KB Output is correct
15 Correct 4017 ms 68992 KB Output is correct
16 Correct 219 ms 6200 KB Output is correct
17 Correct 3418 ms 51368 KB Output is correct
18 Correct 6 ms 3924 KB Output is correct
19 Correct 4278 ms 72120 KB Output is correct
20 Correct 1208 ms 10864 KB Output is correct
21 Correct 1061 ms 9772 KB Output is correct
22 Correct 645 ms 7092 KB Output is correct
23 Correct 31 ms 5592 KB Output is correct
24 Correct 3431 ms 60208 KB Output is correct
25 Correct 993 ms 8524 KB Output is correct
26 Correct 446 ms 6548 KB Output is correct
27 Correct 862 ms 7760 KB Output is correct
28 Correct 18 ms 4740 KB Output is correct
29 Correct 1495 ms 10532 KB Output is correct
30 Correct 2108 ms 17824 KB Output is correct

Subtask #4
0 / 58.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2696 KB Output is correct
3 Correct 2 ms 2692 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 3 ms 2696 KB Output is correct
8 Correct 2 ms 2744 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 5 ms 2644 KB Output is correct
12 Correct 4 ms 2688 KB Output is correct
13 Correct 4 ms 2664 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct
15 Correct 6 ms 2748 KB Output is correct
16 Correct 2 ms 2684 KB Output is correct
17 Correct 5 ms 2648 KB Output is correct
18 Correct 2 ms 2692 KB Output is correct
19 Correct 5 ms 2644 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 4 ms 2688 KB Output is correct
22 Correct 2 ms 2684 KB Output is correct
23 Correct 4 ms 2644 KB Output is correct
24 Correct 2 ms 2644 KB Output is correct
25 Correct 2 ms 2684 KB Output is correct
26 Correct 2 ms 2644 KB Output is correct
27 Correct 2 ms 2644 KB Output is correct
28 Correct 5 ms 2692 KB Output is correct
29 Correct 3 ms 2696 KB Output is correct
30 Correct 3 ms 2644 KB Output is correct
31 Incorrect 3 ms 2644 KB Output isn't correct
32 Halted 0 ms 0 KB -