# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
982976 | 2024-05-15T06:21:53 Z | vjudge1 | 다리 (APIO19_bridges) | C++17 | 110 ms | 25940 KB |
#include <bits/stdc++.h> using namespace std; #define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define rall(s) s.rbegin(),s.rend() #define all(s) s.begin(),s.end() #define pb push_back #define se second #define fi first #define ll long long #define ld long double #define YES cout<<"YES\n" #define Yes cout<<"Yes\n" #define yes cout<<"yes\n" #define NO cout<<"NO\n" #define No cout<<"No\n" #define no cout<<"no\n" const int N = 5e5 + 9 , mod = 1e9 + 7; ll a[N] , b[N] , dp[N] ,p[N] , sz[N] , c[N] , d[N] , ans[N]; vector<pair<int,int>>v[N]; ll get(int x){ return (p[x] == x ? x : get(p[x])); } void join(int x , int y){ x = get(x) , y = get(y); if(x != y){ if(sz[x] < sz[y]) swap(x , y); p[y] = x; sz[x] += sz[y]; } } bool bmp(int i , int j){ return c[i] > c[j]; } struct query{ ll x , y , k; }Q[N]; bool bmp1(query &i , query &j){ return i.y > j.y; } void solve() { ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18; cin>>n>>m; for(i = 1; i <= m; i++){ cin>>a[i]>>b[i]>>c[i]; v[a[i]].pb({b[i] , c[i]}); v[b[i]].pb({a[i] , c[i]}); d[i] = i; } cin>>q; vector<pair<int,int>>vc; for(j = 1; j <= q; j++){ cin>>k>>x>>y; Q[j] = {x , y , j}; if(max(n , m) <= 1000 && q <= 10000){ if(k == 1){ c[x] = y; }else { for(i = 1; i <= n; i++) p[i] = i , sz[i] = 1; for(i = 1; i <= m; i++){ if(c[i] >= y){ join(a[i] , b[i]); } } cout<<sz[get(x)]<<"\n"; } if(j == q) return; } } sort(d + 1 , d + m + 1 , bmp); sort(Q + 1 , Q + q + 1 , bmp1); for(i = 1; i <= n; i++) p[i] = i , sz[i] = 1; l = 1; for(i = 1; i <= m + 1; i++){ j = d[i]; while(l <= q && Q[l].y > c[j]){ ans[Q[l].k] = sz[get(Q[l].x)]; l++; } join(a[j] , b[j]); if(i == m + 1) continue; } for(j = 1; j <= q; j++) cout<<ans[j]<<"\n"; } int main(){ TL; /*#ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif*/ int t = 1; // cin>>t; while(t--) { solve(); } } // Author : حسن
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 12124 KB | Output is correct |
2 | Correct | 6 ms | 12196 KB | Output is correct |
3 | Correct | 53 ms | 12636 KB | Output is correct |
4 | Correct | 8 ms | 12376 KB | Output is correct |
5 | Correct | 12 ms | 12436 KB | Output is correct |
6 | Correct | 10 ms | 12636 KB | Output is correct |
7 | Correct | 13 ms | 12588 KB | Output is correct |
8 | Correct | 11 ms | 12660 KB | Output is correct |
9 | Correct | 14 ms | 12380 KB | Output is correct |
10 | Correct | 10 ms | 12636 KB | Output is correct |
11 | Correct | 11 ms | 12636 KB | Output is correct |
12 | Correct | 11 ms | 12888 KB | Output is correct |
13 | Correct | 13 ms | 12636 KB | Output is correct |
14 | Correct | 13 ms | 12632 KB | Output is correct |
15 | Correct | 14 ms | 12552 KB | Output is correct |
16 | Correct | 11 ms | 12648 KB | Output is correct |
17 | Correct | 14 ms | 12416 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 60 ms | 21588 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 57 ms | 20720 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 110 ms | 25940 KB | Output is correct |
2 | Correct | 35 ms | 16720 KB | Output is correct |
3 | Correct | 42 ms | 19508 KB | Output is correct |
4 | Correct | 33 ms | 19400 KB | Output is correct |
5 | Correct | 86 ms | 24940 KB | Output is correct |
6 | Correct | 90 ms | 25748 KB | Output is correct |
7 | Correct | 67 ms | 24796 KB | Output is correct |
8 | Correct | 68 ms | 21640 KB | Output is correct |
9 | Correct | 70 ms | 21588 KB | Output is correct |
10 | Correct | 68 ms | 21708 KB | Output is correct |
11 | Correct | 82 ms | 24232 KB | Output is correct |
12 | Correct | 82 ms | 24228 KB | Output is correct |
13 | Correct | 92 ms | 24148 KB | Output is correct |
14 | Correct | 80 ms | 24932 KB | Output is correct |
15 | Correct | 81 ms | 24912 KB | Output is correct |
16 | Correct | 88 ms | 25576 KB | Output is correct |
17 | Correct | 95 ms | 25228 KB | Output is correct |
18 | Correct | 92 ms | 25372 KB | Output is correct |
19 | Correct | 105 ms | 25448 KB | Output is correct |
20 | Correct | 80 ms | 24784 KB | Output is correct |
21 | Correct | 86 ms | 25048 KB | Output is correct |
22 | Correct | 102 ms | 25304 KB | Output is correct |
23 | Correct | 67 ms | 23340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 60 ms | 21588 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 12124 KB | Output is correct |
2 | Correct | 6 ms | 12196 KB | Output is correct |
3 | Correct | 53 ms | 12636 KB | Output is correct |
4 | Correct | 8 ms | 12376 KB | Output is correct |
5 | Correct | 12 ms | 12436 KB | Output is correct |
6 | Correct | 10 ms | 12636 KB | Output is correct |
7 | Correct | 13 ms | 12588 KB | Output is correct |
8 | Correct | 11 ms | 12660 KB | Output is correct |
9 | Correct | 14 ms | 12380 KB | Output is correct |
10 | Correct | 10 ms | 12636 KB | Output is correct |
11 | Correct | 11 ms | 12636 KB | Output is correct |
12 | Correct | 11 ms | 12888 KB | Output is correct |
13 | Correct | 13 ms | 12636 KB | Output is correct |
14 | Correct | 13 ms | 12632 KB | Output is correct |
15 | Correct | 14 ms | 12552 KB | Output is correct |
16 | Correct | 11 ms | 12648 KB | Output is correct |
17 | Correct | 14 ms | 12416 KB | Output is correct |
18 | Incorrect | 60 ms | 21588 KB | Output isn't correct |
19 | Halted | 0 ms | 0 KB | - |