oj.uz

답안 #713632

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
713632 2023-03-22T17:20:49 Z bin9638 다리 (APIO19_bridges) C++17
100 / 100
 1552 ms 10896 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define N 100010
#define ii pair<int,int>
#define fs first
#define sc second
#define ld double

struct canh
{
    int u,v,L,id;

    bool operator<(const canh&A)const
    {
        return L>A.L;
    }
}edge[N],g[N];

struct truyvan
{
    int type,id,val,cs;

    bool operator<(const truyvan&A)const
    {
        return val>A.val;
    }
}tv[N];
vector<truyvan>s;

struct DSU
{
    int lab[N]={},dem=0;

    void init()
    {
        memset(lab,-1,sizeof(lab));
        dem=0;
    }

    struct roll
    {
        int u,v,val_u,val_v;
    }luu[N];

    int root_roll_back(int u)
    {
        if(lab[u]<0)
            return u;
        return root_roll_back(lab[u]);
    }

    void update_roll_back(int u,int v)
    {
        if((u=root_roll_back(u))==(v=root_roll_back(v)))
            return;
        if(lab[u]>lab[v])
            swap(u,v);
        luu[++dem]={u,v,lab[u],lab[v]};
        lab[u]+=lab[v];
        lab[v]=u;
    }

    void roll_back()
    {
        for(int i=dem;i>=1;i--)
        {
            lab[luu[i].u]=luu[i].val_u;
            lab[luu[i].v]=luu[i].val_v;
        }
        dem=0;
    }

    int root(int u)
    {
        if(lab[u]<0)
            return u;
        return(lab[u]=root(lab[u]));
    }

    void update(int u,int v)
    {
        if((u=root(u))==(v=root(v)))
            return;
        if(lab[u]>lab[v])
            swap(u,v);
        lab[u]+=lab[v];
        lab[v]=u;
    }
}T;

int kq[N],n,m,q,ktr[N],times,chon[N];
vector<int>lis;

void solve(int l,int r)
{
    for(int i=1;i<=m;i++)
        g[i]=edge[i];
    sort(g+1,g+1+m);
    T.init();
    lis.clear();
    memset(ktr,0,sizeof(ktr));
    for(int i=l;i<=r;i++)
        if(tv[i].type==1)
            ktr[tv[i].id]=i,lis.pb(tv[i].id);
    s.clear();
    for(int i=l;i<=r;i++)
        if(tv[i].type==2)
            s.pb(tv[i]);
    sort(s.begin(),s.end());
    int pos=1;
    for(auto cc:s)
    {
        int u=cc.id,val=cc.val;
        while(pos<=m&&g[pos].L>=val)
        {
            if(ktr[g[pos].id]==0)
                T.update(g[pos].u,g[pos].v);
            pos++;
        }
        times++;
        for(int i=cc.cs;i>=l;i--)
            if(tv[i].type==1&&chon[tv[i].id]!=times)
            {
                chon[tv[i].id]=times;
                if(tv[i].val>=val)
                    T.update_roll_back(edge[tv[i].id].u,edge[tv[i].id].v);
            }
        for(auto k:lis)
            if(chon[k]!=times)
            {
                //cout<<k<<" "<<tv[k].val<<endl;
                chon[k]=times;
                if(edge[k].L>=val)
                    T.update_roll_back(edge[k].u,edge[k].v);
            }
        kq[cc.cs]=-T.lab[T.root_roll_back(u)];
        T.roll_back();
    }
}

int main()
{
    #ifdef SKY
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    #endif // SKY
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>edge[i].u>>edge[i].v>>edge[i].L;
        edge[i].id=i;
    }
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>tv[i].type>>tv[i].id>>tv[i].val;
        tv[i].cs=i;
    }
    for(int pos=1;pos<=q;pos+=1000)
    {
        solve(pos,pos+1000-1);
        for(int i=pos;i<pos+1000;i++)
            if(tv[i].type==1)
                edge[tv[i].id].L=tv[i].val;
    }
    for(int i=1;i<=q;i++)if(kq[i]!=0)cout<<kq[i]<<"\n";
    return 0;
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 23 ms 1388 KB Output is correct
4 Correct 8 ms 1344 KB Output is correct
5 Correct 21 ms 1364 KB Output is correct
6 Correct 20 ms 1336 KB Output is correct
7 Correct 21 ms 1340 KB Output is correct
8 Correct 20 ms 1340 KB Output is correct
9 Correct 19 ms 1364 KB Output is correct
10 Correct 21 ms 1364 KB Output is correct
11 Correct 21 ms 1376 KB Output is correct
12 Correct 21 ms 1332 KB Output is correct
13 Correct 27 ms 1368 KB Output is correct
14 Correct 25 ms 1348 KB Output is correct
15 Correct 23 ms 1372 KB Output is correct
16 Correct 20 ms 1356 KB Output is correct
17 Correct 21 ms 1364 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 916 ms 5028 KB Output is correct
2 Correct 961 ms 7772 KB Output is correct
3 Correct 969 ms 7680 KB Output is correct
4 Correct 1043 ms 7744 KB Output is correct
5 Correct 1018 ms 7724 KB Output is correct
6 Correct 1552 ms 7656 KB Output is correct
7 Correct 1502 ms 7712 KB Output is correct
8 Correct 1519 ms 7856 KB Output is correct
9 Correct 69 ms 4648 KB Output is correct
10 Correct 843 ms 6596 KB Output is correct
11 Correct 797 ms 6672 KB Output is correct
12 Correct 845 ms 7880 KB Output is correct
13 Correct 901 ms 7584 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 773 ms 4380 KB Output is correct
2 Correct 581 ms 5224 KB Output is correct
3 Correct 851 ms 6556 KB Output is correct
4 Correct 719 ms 6840 KB Output is correct
5 Correct 71 ms 4616 KB Output is correct
6 Correct 802 ms 6888 KB Output is correct
7 Correct 676 ms 6964 KB Output is correct
8 Correct 599 ms 6720 KB Output is correct
9 Correct 485 ms 6732 KB Output is correct
10 Correct 450 ms 6684 KB Output is correct
11 Correct 495 ms 6664 KB Output is correct
12 Correct 433 ms 6476 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 965 ms 6724 KB Output is correct
2 Correct 65 ms 3196 KB Output is correct
3 Correct 105 ms 4384 KB Output is correct
4 Correct 53 ms 4420 KB Output is correct
5 Correct 489 ms 6768 KB Output is correct
6 Correct 927 ms 6804 KB Output is correct
7 Correct 473 ms 6604 KB Output is correct
8 Correct 499 ms 4840 KB Output is correct
9 Correct 496 ms 4876 KB Output is correct
10 Correct 494 ms 5104 KB Output is correct
11 Correct 761 ms 5684 KB Output is correct
12 Correct 738 ms 5632 KB Output is correct
13 Correct 776 ms 5872 KB Output is correct
14 Correct 441 ms 6732 KB Output is correct
15 Correct 492 ms 6724 KB Output is correct
16 Correct 968 ms 6924 KB Output is correct
17 Correct 994 ms 6548 KB Output is correct
18 Correct 974 ms 6588 KB Output is correct
19 Correct 970 ms 6492 KB Output is correct
20 Correct 842 ms 6204 KB Output is correct
21 Correct 835 ms 6216 KB Output is correct
22 Correct 938 ms 6728 KB Output is correct
23 Correct 545 ms 6188 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 916 ms 5028 KB Output is correct
2 Correct 961 ms 7772 KB Output is correct
3 Correct 969 ms 7680 KB Output is correct
4 Correct 1043 ms 7744 KB Output is correct
5 Correct 1018 ms 7724 KB Output is correct
6 Correct 1552 ms 7656 KB Output is correct
7 Correct 1502 ms 7712 KB Output is correct
8 Correct 1519 ms 7856 KB Output is correct
9 Correct 69 ms 4648 KB Output is correct
10 Correct 843 ms 6596 KB Output is correct
11 Correct 797 ms 6672 KB Output is correct
12 Correct 845 ms 7880 KB Output is correct
13 Correct 901 ms 7584 KB Output is correct
14 Correct 773 ms 4380 KB Output is correct
15 Correct 581 ms 5224 KB Output is correct
16 Correct 851 ms 6556 KB Output is correct
17 Correct 719 ms 6840 KB Output is correct
18 Correct 71 ms 4616 KB Output is correct
19 Correct 802 ms 6888 KB Output is correct
20 Correct 676 ms 6964 KB Output is correct
21 Correct 599 ms 6720 KB Output is correct
22 Correct 485 ms 6732 KB Output is correct
23 Correct 450 ms 6684 KB Output is correct
24 Correct 495 ms 6664 KB Output is correct
25 Correct 433 ms 6476 KB Output is correct
26 Correct 876 ms 7720 KB Output is correct
27 Correct 1088 ms 7688 KB Output is correct
28 Correct 936 ms 7824 KB Output is correct
29 Correct 706 ms 7728 KB Output is correct
30 Correct 1121 ms 7700 KB Output is correct
31 Correct 1137 ms 7584 KB Output is correct
32 Correct 1127 ms 7848 KB Output is correct
33 Correct 946 ms 7828 KB Output is correct
34 Correct 949 ms 7904 KB Output is correct
35 Correct 952 ms 7840 KB Output is correct
36 Correct 735 ms 7732 KB Output is correct
37 Correct 755 ms 7692 KB Output is correct
38 Correct 726 ms 7872 KB Output is correct
39 Correct 594 ms 7756 KB Output is correct
40 Correct 581 ms 7704 KB Output is correct
41 Correct 585 ms 7856 KB Output is correct
42 Correct 561 ms 7556 KB Output is correct
43 Correct 560 ms 7676 KB Output is correct
44 Correct 546 ms 7492 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 23 ms 1388 KB Output is correct
4 Correct 8 ms 1344 KB Output is correct
5 Correct 21 ms 1364 KB Output is correct
6 Correct 20 ms 1336 KB Output is correct
7 Correct 21 ms 1340 KB Output is correct
8 Correct 20 ms 1340 KB Output is correct
9 Correct 19 ms 1364 KB Output is correct
10 Correct 21 ms 1364 KB Output is correct
11 Correct 21 ms 1376 KB Output is correct
12 Correct 21 ms 1332 KB Output is correct
13 Correct 27 ms 1368 KB Output is correct
14 Correct 25 ms 1348 KB Output is correct
15 Correct 23 ms 1372 KB Output is correct
16 Correct 20 ms 1356 KB Output is correct
17 Correct 21 ms 1364 KB Output is correct
18 Correct 916 ms 5028 KB Output is correct
19 Correct 961 ms 7772 KB Output is correct
20 Correct 969 ms 7680 KB Output is correct
21 Correct 1043 ms 7744 KB Output is correct
22 Correct 1018 ms 7724 KB Output is correct
23 Correct 1552 ms 7656 KB Output is correct
24 Correct 1502 ms 7712 KB Output is correct
25 Correct 1519 ms 7856 KB Output is correct
26 Correct 69 ms 4648 KB Output is correct
27 Correct 843 ms 6596 KB Output is correct
28 Correct 797 ms 6672 KB Output is correct
29 Correct 845 ms 7880 KB Output is correct
30 Correct 901 ms 7584 KB Output is correct
31 Correct 773 ms 4380 KB Output is correct
32 Correct 581 ms 5224 KB Output is correct
33 Correct 851 ms 6556 KB Output is correct
34 Correct 719 ms 6840 KB Output is correct
35 Correct 71 ms 4616 KB Output is correct
36 Correct 802 ms 6888 KB Output is correct
37 Correct 676 ms 6964 KB Output is correct
38 Correct 599 ms 6720 KB Output is correct
39 Correct 485 ms 6732 KB Output is correct
40 Correct 450 ms 6684 KB Output is correct
41 Correct 495 ms 6664 KB Output is correct
42 Correct 433 ms 6476 KB Output is correct
43 Correct 965 ms 6724 KB Output is correct
44 Correct 65 ms 3196 KB Output is correct
45 Correct 105 ms 4384 KB Output is correct
46 Correct 53 ms 4420 KB Output is correct
47 Correct 489 ms 6768 KB Output is correct
48 Correct 927 ms 6804 KB Output is correct
49 Correct 473 ms 6604 KB Output is correct
50 Correct 499 ms 4840 KB Output is correct
51 Correct 496 ms 4876 KB Output is correct
52 Correct 494 ms 5104 KB Output is correct
53 Correct 761 ms 5684 KB Output is correct
54 Correct 738 ms 5632 KB Output is correct
55 Correct 776 ms 5872 KB Output is correct
56 Correct 441 ms 6732 KB Output is correct
57 Correct 492 ms 6724 KB Output is correct
58 Correct 968 ms 6924 KB Output is correct
59 Correct 994 ms 6548 KB Output is correct
60 Correct 974 ms 6588 KB Output is correct
61 Correct 970 ms 6492 KB Output is correct
62 Correct 842 ms 6204 KB Output is correct
63 Correct 835 ms 6216 KB Output is correct
64 Correct 938 ms 6728 KB Output is correct
65 Correct 545 ms 6188 KB Output is correct
66 Correct 876 ms 7720 KB Output is correct
67 Correct 1088 ms 7688 KB Output is correct
68 Correct 936 ms 7824 KB Output is correct
69 Correct 706 ms 7728 KB Output is correct
70 Correct 1121 ms 7700 KB Output is correct
71 Correct 1137 ms 7584 KB Output is correct
72 Correct 1127 ms 7848 KB Output is correct
73 Correct 946 ms 7828 KB Output is correct
74 Correct 949 ms 7904 KB Output is correct
75 Correct 952 ms 7840 KB Output is correct
76 Correct 735 ms 7732 KB Output is correct
77 Correct 755 ms 7692 KB Output is correct
78 Correct 726 ms 7872 KB Output is correct
79 Correct 594 ms 7756 KB Output is correct
80 Correct 581 ms 7704 KB Output is correct
81 Correct 585 ms 7856 KB Output is correct
82 Correct 561 ms 7556 KB Output is correct
83 Correct 560 ms 7676 KB Output is correct
84 Correct 546 ms 7492 KB Output is correct
85 Correct 1218 ms 10896 KB Output is correct
86 Correct 118 ms 6636 KB Output is correct
87 Correct 64 ms 6732 KB Output is correct
88 Correct 691 ms 9256 KB Output is correct
89 Correct 1195 ms 10728 KB Output is correct
90 Correct 708 ms 8924 KB Output is correct
91 Correct 1006 ms 7584 KB Output is correct
92 Correct 1049 ms 7772 KB Output is correct
93 Correct 1544 ms 7608 KB Output is correct
94 Correct 1171 ms 9096 KB Output is correct
95 Correct 1146 ms 9272 KB Output is correct
96 Correct 1146 ms 8944 KB Output is correct
97 Correct 565 ms 9164 KB Output is correct
98 Correct 562 ms 8740 KB Output is correct
99 Correct 1288 ms 10488 KB Output is correct
100 Correct 1290 ms 10432 KB Output is correct
101 Correct 1326 ms 10648 KB Output is correct
102 Correct 1313 ms 10628 KB Output is correct
103 Correct 1153 ms 9548 KB Output is correct
104 Correct 1158 ms 9520 KB Output is correct
105 Correct 966 ms 9296 KB Output is correct
106 Correct 832 ms 8916 KB Output is correct
107 Correct 960 ms 9496 KB Output is correct
108 Correct 1193 ms 10316 KB Output is correct
109 Correct 776 ms 8196 KB Output is correct