oj.uz

답안 #440401

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
440401 2021-07-02T08:34:15 Z VladM 다리 (APIO19_bridges) C++14
29 / 100
 1183 ms 5452 KB 
#include <bits/stdc++.h>

using namespace std;

#define DIM 50007

#define INF 1000000007

typedef pair<long long, long long> pll;

long long vis[DIM], res, n, m, u, v, w[DIM], t[4*DIM], it, s, W, l, r, mid, L, R, mn, q, T;

vector<pll> vec[DIM];

void BuildTree(long long v, long long tl, long long tr)
{
    if(tl==tr)
    {
        t[v]=w[tl];
        return;
    }
    long long tm=(tl+tr)>>1;
    BuildTree(2*v+1, tl, tm);
    BuildTree(2*v+2, tm+1, tr);
    t[v]=min(t[2*v+1], t[2*v+2]);
    return;
}

void update(long long v, long long tl, long long tr, long long x, long long val)
{
    if(x<tl || tr<x) return;
    if(tl==tr)
    {
        t[v]=val;
        return;
    }
    long long tm=(tl+tr)>>1;
    update(2*v+1, tl, tm, x, val);
    update(2*v+2, tm+1, tr, x, val);
    t[v]=min(t[2*v+1], t[2*v+2]);
    return;
}

long long get_min(long long v, long long tl, long long tr, long long L, long long R)
{
    if(tr<L || R<tl) return INF;
    if(L<=tl && tr<=R) return t[v];
    long long tm=(tl+tr)>>1;
    long long mn1=get_min(2*v+1, tl, tm, L, R);
    long long mn2=get_min(2*v+2, tm+1, tr, L, R);
    return min(mn1, mn2);
}

void dfs(long long v, long long car)
{
    vis[v]=1;
    for(auto to : vec[v])
    {
        if(vis[to.first]==1 || w[to.second]<car) continue;
        dfs(to.first, car);
    }
    return;
}

void solve()
{
    for(int i=1; i<=m; i++)
    {
        cin>>u>>v>>w[i];
        vec[u].push_back({v, i});
        vec[v].push_back({u, i});
    }
    cin>>q;
    while(q--)
    {
        cin>>T;
        if(T==1)
        {
            cin>>it>>r;
            w[it]=r;
            continue;
        }
        cin>>s>>W;
        for(int i=1; i<=n; i++) vis[i]=0;
        vis[s]=1;
        dfs(s, W);
        res=0;
        for(int i=1; i<=n; i++) res+=vis[i];
        cout<<res<<endl;
    }
    return;
}

int main()
{
    cin>>n>>m;
    if(n<=1000 && m<=1000)
    {
        solve();
        return 0;
    }
    for(int i=1; i<=m; i++)
    {
        cin>>u>>v>>w[i];
    }
    if(n!=1) BuildTree(0, 1, m);
    cin>>q;
    while(q--)
    {
        cin>>T;
        if(T==1)
        {
            cin>>it>>r;
            if(n!=1) update(0, 1, m, it, r);
            continue;
        }
        cin>>s>>W;
        if(n==1)
        {
            cout<<1<<endl;
            continue;
        }
        if(s==n) R=n;
        else
        {
            l=s;
            r=m;
            while(l<r)
            {
                mid=(l+r+1)>>1;
                mn=get_min(0, 1, m, s, mid);
                if(mn<W) r=mid-1;
                else l=mid;
            }
            if(l==s)
            {
                mn=get_min(0, 1, m, s, s);
                if(mn>=W) R=s+1;
                else R=s;
            }
            else
            {
                R=l+1;
            }
        }
        if(s==1) L=1;
        else
        {
            l=1;
            r=s-1;
            while(l<r)
            {
                mid=(l+r)>>1;
                mn=get_min(0, 1, m, mid, s-1);
                if(mn<W) l=mid+1;
                else r=mid;
            }
            if(l==s-1)
            {
                mn=get_min(0, 1, m, l, l);
                if(mn<W) L=s;
                else L=s-1;
            }
            else L=l;
        }
        cout<<R-L+1<<endl;
    }
    return 0;
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1356 KB Output is correct
3 Correct 53 ms 1484 KB Output is correct
4 Correct 26 ms 1612 KB Output is correct
5 Correct 21 ms 1500 KB Output is correct
6 Correct 21 ms 1484 KB Output is correct
7 Correct 19 ms 1484 KB Output is correct
8 Correct 24 ms 1612 KB Output is correct
9 Correct 25 ms 1484 KB Output is correct
10 Correct 19 ms 1484 KB Output is correct
11 Correct 20 ms 1496 KB Output is correct
12 Correct 19 ms 1500 KB Output is correct
13 Correct 22 ms 1504 KB Output is correct
14 Correct 22 ms 1484 KB Output is correct
15 Correct 28 ms 1484 KB Output is correct
16 Correct 20 ms 1496 KB Output is correct
17 Correct 19 ms 1484 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 652 ms 3052 KB Output is correct
2 Correct 642 ms 2912 KB Output is correct
3 Correct 665 ms 2884 KB Output is correct
4 Correct 651 ms 2940 KB Output is correct
5 Correct 678 ms 3012 KB Output is correct
6 Correct 726 ms 3200 KB Output is correct
7 Correct 724 ms 3148 KB Output is correct
8 Correct 725 ms 3072 KB Output is correct
9 Correct 252 ms 1600 KB Output is correct
10 Correct 683 ms 3040 KB Output is correct
11 Correct 663 ms 3036 KB Output is correct
12 Correct 1183 ms 3376 KB Output is correct
13 Correct 319 ms 2960 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 108 ms 5452 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 652 ms 3052 KB Output is correct
2 Correct 642 ms 2912 KB Output is correct
3 Correct 665 ms 2884 KB Output is correct
4 Correct 651 ms 2940 KB Output is correct
5 Correct 678 ms 3012 KB Output is correct
6 Correct 726 ms 3200 KB Output is correct
7 Correct 724 ms 3148 KB Output is correct
8 Correct 725 ms 3072 KB Output is correct
9 Correct 252 ms 1600 KB Output is correct
10 Correct 683 ms 3040 KB Output is correct
11 Correct 663 ms 3036 KB Output is correct
12 Correct 1183 ms 3376 KB Output is correct
13 Correct 319 ms 2960 KB Output is correct
14 Incorrect 612 ms 2444 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1356 KB Output is correct
3 Correct 53 ms 1484 KB Output is correct
4 Correct 26 ms 1612 KB Output is correct
5 Correct 21 ms 1500 KB Output is correct
6 Correct 21 ms 1484 KB Output is correct
7 Correct 19 ms 1484 KB Output is correct
8 Correct 24 ms 1612 KB Output is correct
9 Correct 25 ms 1484 KB Output is correct
10 Correct 19 ms 1484 KB Output is correct
11 Correct 20 ms 1496 KB Output is correct
12 Correct 19 ms 1500 KB Output is correct
13 Correct 22 ms 1504 KB Output is correct
14 Correct 22 ms 1484 KB Output is correct
15 Correct 28 ms 1484 KB Output is correct
16 Correct 20 ms 1496 KB Output is correct
17 Correct 19 ms 1484 KB Output is correct
18 Correct 652 ms 3052 KB Output is correct
19 Correct 642 ms 2912 KB Output is correct
20 Correct 665 ms 2884 KB Output is correct
21 Correct 651 ms 2940 KB Output is correct
22 Correct 678 ms 3012 KB Output is correct
23 Correct 726 ms 3200 KB Output is correct
24 Correct 724 ms 3148 KB Output is correct
25 Correct 725 ms 3072 KB Output is correct
26 Correct 252 ms 1600 KB Output is correct
27 Correct 683 ms 3040 KB Output is correct
28 Correct 663 ms 3036 KB Output is correct
29 Correct 1183 ms 3376 KB Output is correct
30 Correct 319 ms 2960 KB Output is correct
31 Incorrect 612 ms 2444 KB Output isn't correct
32 Halted 0 ms 0 KB -