fork download
copy 
  1. /**
  2.  *    author:  orzvanh14 (  )
  3.  *    created: 23.12.2022 10:08:02
  4.  *    too lazy to update time
  5. **/
  6. // i wants to take ioi
  7. //binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong
  8. #include <bits/stdc++.h>
  9.  
  10. using namespace std;
  11.  
  12. #define int long long
  13. #define nn "\n"
  14. #define pi pair<int, int>
  15. #define fi first
  16. #define se second
  17. #define lb lower_bound
  18. #define ub upper_bound
  19. #define eb emplace_back
  20. #define pb push_back
  21. #define TASK " "
  22.  
  23. #define ms(a, x) memset(a, x, sizeof(a))
  24. #define all(a) a.begin(), a.end()
  25. #define All(a, n) a + 1, a + 1 + n
  26.  
  27. #define LOG 19
  28.  
  29.  
  30. const int INF = 1e18;
  31. const int mod = 1e9+7;
  32. const int maxN = 1e6 + 5;
  33. const int N = 1e5  + 5;
  34. int MOD = 998244353;
  35. int bit[200000];
  36. struct node{
  37. 	int kc, u, hk;
  38. 	bool operator<(const node& other) const {
  39.         return kc > other.kc;
  40.     }
  41. };
  42. struct edge{
  43. 	int u, v, w;
  44. 	bool operator<(const edge& other) const {
  45.         return w < other.w;
  46.     }
  47. } edge[N];
  48. vector<pi> adj[N];
  49. bool vis[N];
  50. int n, m;
  51. int tp = 0;
  52. int tungay[N];
  53. void nhap(){
  54.     cin >> n >> m;
  55.     for(int i =1; i <= m; i++){
  56.         int a, b, c;
  57.         cin >>a >> b >> c;
  58.         adj[a].eb(b, c);
  59.         adj[b].eb(a, c);
  60.         edge[i].u = a;
  61.         edge[i].v = b, edge[i].w = c;
  62.     }
  63. }
  64. bool bfs(int mid){
  65.     for(int i = 1; i <= n; i++){
  66.         vis[i] = 0;
  67.         tungay[i] = -1;
  68.     }
  69.     for(int i = 1; i <= n; i++){
  70.         if(!vis[i]){
  71.             queue<int> q;
  72.             q.push(i);
  73.             vis[i] = 1;
  74.             tungay[i] = 0;
  75.             while(!q.empty()){
  76.                 int u = q.front();
  77.                 q.pop();
  78.                 for(auto [v, w] : adj[u]){
  79.                     if(!vis[v] && w > mid){
  80.                         q.push(v);
  81.                         vis[v] = 1;
  82.                         tungay[v] = !tungay[u];
  83.                     }
  84.                     else if(tungay[u] == tungay[v] && w > mid){
  85.                         return 0;
  86.                     }
  87.                 }
  88.             }
  89.         }
  90.     }
  91.     return 1;
  92. }
  93. void solve(){
  94.     int l = 0, r = 1e14;
  95.     int ans = 0;
  96.     while(l <= r){
  97.         int m = l + r >> 1;
  98.         if(bfs(m)){
  99.             ans = m;
  100.             r = m- 1;
  101.         }
  102.         else l = m + 1;
  103.     }
  104.     cout << ans << nn;
  105. }
  106. signed main() {
  107. 	// freopen("piggyback.in", "r", stdin);
  108. 	// freopen("piggyback.out", "w", stdout);
  109. 	ios_base::sync_with_stdio(0);
  110. 	cin.tie(0);
  111. 	cout.tie(0);
  112.     nhap();
  113.     solve();
  114. 	return (0 ^ 0);
  115.  
  116. }
  117.  
Success #stdin #stdout 0.01s 6324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/i7Z0a4
language:
C++14 (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!