Submission #743699

#	Time	Username	Problem	Language	Result	Execution time	Memory
743699		fanwen	Relay Marathon (NOI20_relaymarathon)	C++17	100 / 100	5546 ms	209804 KiB

RelayMarathon

/**
*   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 int long long
#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;
bool dd[MAXN];
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 SegmentTree {
		vector <int> it;
		SegmentTree() = default;
		SegmentTree(int n) : it(4 * n + 5, 2e9) {}
		void update(int idx, int l, int r, int u, int x) {
			if(l > u || r < u) return;
			if(l == r) return void(minimize(it[idx], x));
			int mid = (l + r) >> 1;
			update(idx << 1, l, mid, u, x);
			update(idx << 1 | 1, mid + 1, r, u, x);
			it[idx] = min(it[idx << 1], it[idx << 1 | 1]);
		}
		int get(int idx, int l, int r, int u, int v) {
			if(l > v || r < u) return 2e9;
			if(l >= u && r <= v) return it[idx];
			int mid = (l + r) >> 1;
			return min(get(idx << 1, l, mid, u, v), get(idx << 1 | 1, mid + 1, r, u, v));
		}
	};
	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);
		}
		// return;
		SegmentTree IT(N);
		int ans = 2e9;
		int j = 0;
		sort (val.begin(), val.end(), [](Data A, Data B) {
			return A.u < B.u;
		});
		For (i, 0, (int) val.size()) {
			while(j < i && val[j].u < val[i].u) {
				IT.update(1, 1, N, val[j].v, val[j].w);
				j++;
			}
			minimize(ans, val[i].w + min({IT.get(1, 1, N, 1, val[i].u - 1), 
										  IT.get(1, 1, N, val[i].u + 1, val[i].v - 1), 
										  IT.get(1, 1, N, val[i].v + 1, N)}));
		}
		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 (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 25 / 25
• Subtask 4: 58 / 58