QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#274463 | #7883. Takeout Delivering | _whb# | TL | 1ms | 5492kb | C++20 | 2.2kb | 2023-12-03 15:45:52 | 2023-12-03 15:45:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std ;
const int N = 3e5 + 5, M = 1e6 + 5 ;
using ll = long long ;
//快读板子(不能读负数)
const int MS = 1e7 + 5;
namespace fast_IO {
char buf[MS], *s, *t;
char getchar() {
return (s == t) && (t = (s = buf) + fread(buf, 1, MS, stdin)), s == t ? -1 : *s++;
}
int read() {
int num = 0;
char c;
while ((c = getchar()) != '-' && c != '+' && (c < '0' || c > '9') && ~c);
num = c ^ 48;
while ((c = getchar()) >= '0' && c <= '9')
num = (num << 1) + (num << 3) + (c ^ 48);
return num;
}
}
int n, m ;
int fa[N] ;
struct Edge
{
int x, y, z ;
} e[M] ;
int id[M] ;
int get(int x) { return x == fa[x] ? x : fa[x] = get(fa[x]) ; }
void merge(int x, int y)
{
int l = get(x), r = get(y) ;
if(l != r) fa[r] = l ;
}
inline bool isUni(int x, int y)
{
int l = get(x), r = get(y) ;
return l == r ;
}
bool check(int mid)
{
for(int i = 1; i <= n; ++ i) fa[i] = i ;
for(int i = m, j = 1; i >= 1; -- i)
{
if(e[id[i]].z > mid) continue ;
while(j <= m && e[id[j]].z <= mid - e[id[i]].z && e[id[j]].z <= e[id[i]].z)
merge(e[id[j]].x, e[id[j]].y), j ++ ;
// cout << mid << ' ' << i << ' ' << j << ' ' << isUni(1, n) << '\n' ;
int x = e[id[i]].x, y = e[id[i]].y ;
if(isUni(1, x) && isUni(n, y) || isUni(1, y) && isUni(n, x) || isUni(1, n))
return 1 ;
}
return 0 ;
}
int main()
{
// ios::sync_with_stdio(false) ;
// cin.tie(nullptr) ;
// cin >> n >> m ;
n = fast_IO::read(), m = fast_IO::read() ;
for(int i = 1; i <= m; ++ i)
{
int x, y, z ;
//cin >> x >> y >> z ;
x = fast_IO::read(), y = fast_IO::read(), z = fast_IO::read() ;
e[i] = {x, y, z} ; id[i] = i ;
}
sort(id + 1, id + m + 1, [&](int x, int y) {
return e[x].z < e[y].z ;
}) ;
if(m == 1) return cout << e[1].z << '\n', 0 ;
// for(int i = 1; i <= m; ++ i) cout << id[i] << " \n"[i == m] ;
int l = e[id[1]].z, r = e[id[m]].z + e[id[m - 1]].z ;
// cout << l << ' ' << r << '\n' ;
while(l < r)
{
int mid = (l + r) >> 1 ;
if(check(mid)) r = mid ;
else l = mid + 1 ;
}
cout << l << '\n' ;
return 0 ;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5492kb
input:
4 6 1 2 2 1 3 4 1 4 7 2 3 1 2 4 3 3 4 9
output:
5
result:
ok 1 number(s): "5"
Test #2:
score: -100
Time Limit Exceeded
input:
300000 299999 80516 80517 597830404 110190 110191 82173886 218008 218009 954561262 250110 250111 942489774 66540 66541 156425292 34947 34948 239499776 273789 273790 453201232 84428 84429 439418398 98599 98600 326095035 55636 55637 355015760 158611 158612 684292473 43331 43332 43265001 171621 171622 ...