oj.uz

답안 #983017

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
983017 2024-05-15T07:05:48 Z vjudge1 다리 (APIO19_bridges) C++17
43 / 100
 644 ms 27816 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] , t[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 pushup(int i){
    t[i] = min(t[2 * i] , t[2 * i + 1]);
}

void add(int i , int l , int r , int tl , int tr , ll x){
    int m = (l + r) / 2;
    if(l > tr || r < tl) return;
    if(l >= tl && r <= tr){
        t[i] = x;
    }else {
        add(2 * i , l , m , tl , tr , x);
        add(2 * i + 1 , m + 1 , r , tl , tr , x);
        pushup(i);
    }
}

ll get(int i , int l , int r , int tl , int tr){
    int m = (l + r) / 2;
    if(l > tr || r < tl) return 1e18;
    if(l >= tl && r <= tr){
        return t[i];
    }else {
        return min(get(2 * i , l , m , tl , tr) , get(2 * i + 1 , m + 1 , r , tl , tr));
    }
}

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]});
        s += (min(a[i] , b[i]) != i || max(b[i] , a[i]) != i + 1);
        d[i] = i;
    }
    cin>>q;
    s = (s == 0 && m == n - 1);
    if(s)
        for(i = 1; i <= m; i++)
            add(1 , 1 , m , i , i , c[i]);
    vector<pair<int,int>>vc;
    for(j = 1; j <= q; j++){
        cin>>k>>x>>y;
        if(s){
            if(k == 1){
                c[x] = y;
                add(1 , 1 , m , x , x , c[x]);
            }else {
                ll L = x, R=  x;
                if(c[x - 1] >= y && x != 1){
                    r = x - 1;
                    l = 1;
                    while(l != r){
                        ll M = (l + r) / 2;
                        if(get(1 , 1 , m , M , x - 1) >= y)
                            r = M;
                        else
                            l = M + 1;
                    }
                    L = l;
                }
                if(x <= m && c[x] >= y){
                    l = x;
                    r = m;
                    while(l != r){
                        ll M = (l + r + 1) / 2;
                        if(get(1 , 1 , m , x , M) >= y)
                            l = M;
                        else
                            r = M - 1;
                    }
                    R = l + 1;
                }
                cout<<R -  L + 1<<"\n";
            }
            if(j == q)
                return;
            continue;
        }
        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

bridges.cpp: In function 'void solve()':
bridges.cpp:78:46: warning: unused variable 'f' [-Wunused-variable]
   78 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |                                              ^
bridges.cpp:78:58: warning: unused variable 'mx' [-Wunused-variable]
   78 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |                                                          ^~
bridges.cpp:78:67: warning: unused variable 'mn' [-Wunused-variable]
   78 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |                                                                   ^~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 13560 KB Output is correct
2 Correct 6 ms 13404 KB Output is correct
3 Correct 52 ms 13660 KB Output is correct
4 Correct 7 ms 13404 KB Output is correct
5 Correct 10 ms 13616 KB Output is correct
6 Correct 10 ms 13656 KB Output is correct
7 Correct 9 ms 13660 KB Output is correct
8 Correct 10 ms 13660 KB Output is correct
9 Correct 10 ms 13740 KB Output is correct
10 Correct 10 ms 13656 KB Output is correct
11 Correct 11 ms 12380 KB Output is correct
12 Correct 10 ms 13660 KB Output is correct
13 Correct 14 ms 13660 KB Output is correct
14 Correct 15 ms 13912 KB Output is correct
15 Correct 13 ms 13656 KB Output is correct
16 Correct 10 ms 13616 KB Output is correct
17 Correct 11 ms 13660 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 191 ms 17972 KB Output is correct
2 Correct 199 ms 20440 KB Output is correct
3 Correct 195 ms 20484 KB Output is correct
4 Correct 190 ms 20560 KB Output is correct
5 Correct 202 ms 20552 KB Output is correct
6 Correct 384 ms 20316 KB Output is correct
7 Correct 402 ms 20504 KB Output is correct
8 Correct 363 ms 20308 KB Output is correct
9 Correct 26 ms 14932 KB Output is correct
10 Correct 275 ms 19540 KB Output is correct
11 Correct 248 ms 19332 KB Output is correct
12 Correct 644 ms 20444 KB Output is correct
13 Correct 132 ms 20252 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 51 ms 19536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 24176 KB Output is correct
2 Correct 26 ms 13660 KB Output is correct
3 Correct 46 ms 21064 KB Output is correct
4 Correct 34 ms 20868 KB Output is correct
5 Correct 63 ms 26704 KB Output is correct
6 Correct 86 ms 27816 KB Output is correct
7 Correct 71 ms 26452 KB Output is correct
8 Correct 61 ms 23376 KB Output is correct
9 Correct 62 ms 23584 KB Output is correct
10 Correct 61 ms 23320 KB Output is correct
11 Correct 78 ms 25924 KB Output is correct
12 Correct 75 ms 25936 KB Output is correct
13 Correct 74 ms 25936 KB Output is correct
14 Correct 63 ms 26448 KB Output is correct
15 Correct 71 ms 26540 KB Output is correct
16 Correct 86 ms 27264 KB Output is correct
17 Correct 86 ms 27180 KB Output is correct
18 Correct 87 ms 27348 KB Output is correct
19 Correct 90 ms 27400 KB Output is correct
20 Correct 81 ms 26504 KB Output is correct
21 Correct 82 ms 26484 KB Output is correct
22 Correct 97 ms 27372 KB Output is correct
23 Correct 62 ms 24860 KB Output is correct

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 191 ms 17972 KB Output is correct
2 Correct 199 ms 20440 KB Output is correct
3 Correct 195 ms 20484 KB Output is correct
4 Correct 190 ms 20560 KB Output is correct
5 Correct 202 ms 20552 KB Output is correct
6 Correct 384 ms 20316 KB Output is correct
7 Correct 402 ms 20504 KB Output is correct
8 Correct 363 ms 20308 KB Output is correct
9 Correct 26 ms 14932 KB Output is correct
10 Correct 275 ms 19540 KB Output is correct
11 Correct 248 ms 19332 KB Output is correct
12 Correct 644 ms 20444 KB Output is correct
13 Correct 132 ms 20252 KB Output is correct
14 Incorrect 51 ms 19536 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 13560 KB Output is correct
2 Correct 6 ms 13404 KB Output is correct
3 Correct 52 ms 13660 KB Output is correct
4 Correct 7 ms 13404 KB Output is correct
5 Correct 10 ms 13616 KB Output is correct
6 Correct 10 ms 13656 KB Output is correct
7 Correct 9 ms 13660 KB Output is correct
8 Correct 10 ms 13660 KB Output is correct
9 Correct 10 ms 13740 KB Output is correct
10 Correct 10 ms 13656 KB Output is correct
11 Correct 11 ms 12380 KB Output is correct
12 Correct 10 ms 13660 KB Output is correct
13 Correct 14 ms 13660 KB Output is correct
14 Correct 15 ms 13912 KB Output is correct
15 Correct 13 ms 13656 KB Output is correct
16 Correct 10 ms 13616 KB Output is correct
17 Correct 11 ms 13660 KB Output is correct
18 Correct 191 ms 17972 KB Output is correct
19 Correct 199 ms 20440 KB Output is correct
20 Correct 195 ms 20484 KB Output is correct
21 Correct 190 ms 20560 KB Output is correct
22 Correct 202 ms 20552 KB Output is correct
23 Correct 384 ms 20316 KB Output is correct
24 Correct 402 ms 20504 KB Output is correct
25 Correct 363 ms 20308 KB Output is correct
26 Correct 26 ms 14932 KB Output is correct
27 Correct 275 ms 19540 KB Output is correct
28 Correct 248 ms 19332 KB Output is correct
29 Correct 644 ms 20444 KB Output is correct
30 Correct 132 ms 20252 KB Output is correct
31 Incorrect 51 ms 19536 KB Output isn't correct
32 Halted 0 ms 0 KB -