oj.uz

답안 #861963

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
861963 2023-10-17T09:30:48 Z onepunchac168 다리 (APIO19_bridges) C++14
100 / 100
 1596 ms 7000 KB 
//------------------------------------\\
//   ------------------------------   \\
//  |  created by Dinh Manh Hung   |  \\
//  |      tht.onepunchac168       |  \\
//  |     THPT CHUYEN HA TINH      |  \\
//  |      HA TINH, VIET NAM       |  \\
//  |           Siuuu              |  \\
//   ------------------------------   \\
//------------------------------------\\
 
#include <bits/stdc++.h>
using namespace std;
 
#define            task     ""
#define       file(name)    if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define             ldb     long double
#define              pb     push_back
#define              eb     emplace_back
#define              fi     first
#define              se     second
#define           all(x)    begin(x),end(x)
#define       uniquev(v)    v.resize(unique(all(v))-v.begin())
#define       rep(i,a,b)    for (int i=a;i<=b;i++)
#define        cntbit(v)    __builtin_popcountll(v)
#define         gcd(a,b)    __gcd(a,b)
#define         lcm(a,b)    ((1LL*a*b)/__gcd(a,b))
#define          mask(x)    (1LL<<(x))
#define     readbit(x,i)    ((x>>i)&1)
#define             Yes     cout << "Yes"
#define             YES     cout << "YES"
#define              No     cout << "No"
#define              NO     cout << "NO"
 
typedef int ll;
typedef pair <ll,ll> ii;
typedef pair <ll,ii> iii;
typedef pair <ii,ii> iiii;
 
ll dx[]= {1,-1,0,0,1,-1,1,-1};
ll dy[]= {0,0,-1,1,1,-1,-1,1};
 
const ldb PI = acos (-1);
//const ll mod=978846151;
//const ll base=29;
const ll mod=1e9+7;
const char nl = '\n';
 
inline int ReadInt()
{
    char co;
    for (co = getchar(); co < '0' || co > '9'; co = getchar());
    int xo = co - '0';
    for (co = getchar(); co >= '0' && co <= '9'; co = getchar())
        xo = (xo<<1) + (xo<<3) + co - '0';
    return xo;
}
 
void WriteInt(int xo)
{
    if (xo > 9)
        WriteInt(xo / 10);
    putchar(xo % 10 + '0');
}
 
// DEBUG
/*
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
 
 
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
*/
 
/* END OF TEMPLATE*/
 
// ================= Solution =================//
 
 
void onepunchac168();
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    file(task);
    int tests;
    tests=1;
    //cin>>tests;
    while (tests--)
    {
        onepunchac168();
    }
}
 
const int N=5e4+4;
const int M=1e5+5;
const int BLOCK=1000;
int n,m,q;
ll ua[M],va[M],da[M];
ll t[M],a1[M],a2[M];
bool check[M];
ll ans[M];
bool ck[M];
struct DSU{
    int lab[N];
    void makeset (int u)
    {
        lab[u]=-1;
    }
    ll findset(int u)
    {
        if (lab[u]<0)
        {
            return u;
        }
        return lab[u]=findset(lab[u]);
    }
    void Union(int r,int s)
    {
        if (lab[r]>lab[s])
        {
            swap(r,s);
        }
        lab[r]+=lab[s];
        lab[s]=r;
    }
} dsu,dsua;
void onepunchac168()
{
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        cin>>ua[i]>>va[i]>>da[i];
    }
    cin>>q;
    for (int i=1;i<=q;i++)
    {
        cin>>t[i]>>a1[i]>>a2[i];
    }
    for (int i=0;i<=q/BLOCK;i++)
    {
        int left=max(1,i*BLOCK);
        int right=min(q,(i+1)*BLOCK-1);
        vector <iii> cnt;
        vector <ii> tmp;
        for (int j=1;j<=m;j++)
        {
            check[j]=0;
        }
        for (int j=1;j<=n;j++)
        {
            dsu.makeset(j);
        }
        for (int j=left;j<=right;j++)
        {
            if (t[j]==1)
            {
                check[a1[j]]=1;
            }
            else
            {
                tmp.pb({a2[j],j});
            }
 
        }
        for (int j=1;j<=m;j++)
        {
            if (check[j]==1)
            {
                continue;
            }
            cnt.pb({da[j],{ua[j],va[j]}});
        }
        sort (cnt.begin(),cnt.end(),greater <iii> ());
        sort (tmp.begin(),tmp.end(),greater <ii> ());
        ll ida=0;
        for (auto v:tmp)
        {
            int id=v.se;
            int s=a1[id];
            while (ida<cnt.size()&&cnt[ida].fi>=v.fi)
            {
                int r=dsu.findset(cnt[ida].se.fi);
                int s=dsu.findset(cnt[ida].se.se);
                if (r!=s)
                {
                    dsu.Union(r,s);
                }
                ida++;
            }
            vector <ll> opt;
            vector <ii> target;
            opt.pb(dsu.findset(s));
            for (int j=id-1;j>=left;j--)
            {
                if (t[j]==1&&ck[a1[j]]==0)
                {
                    ck[a1[j]]=1;
                    if (a2[j]>=v.fi){
                        target.pb({ua[a1[j]],va[a1[j]]});
                        opt.pb(dsu.findset(ua[a1[j]]));
                        opt.pb(dsu.findset(va[a1[j]]));
                    }
                }
            }
            for (int j=id+1;j<=right;j++)
            {
                if (t[j]==1)
                {
                    if (ck[a1[j]]==0)
                    {
                        ck[a1[j]]=1;
                        if (da[a1[j]]>=v.fi)
                        {
                            target.pb({ua[a1[j]],va[a1[j]]});
                            opt.pb(dsu.findset(ua[a1[j]]));
                            opt.pb(dsu.findset(va[a1[j]]));
                        }
                    }
                }
            }
            for (auto v:opt)
            {
                dsua.makeset(v);
                dsua.lab[v]=dsu.lab[v];
            }
            for (auto v:target)
            {
                int r=dsu.findset(v.fi);
                int ss=dsu.findset(v.se);
                r=dsua.findset(r);
                ss=dsua.findset(ss);
                if (r!=ss)
                {
                    dsua.Union(r,ss);
                }
            }
            int r=dsu.findset(s);
            int ss=dsua.findset(r);
            ans[id]=-dsua.lab[ss];
            for (int j=left;j<=right;j++)
            {
                if (t[j]==1)
                {
                    ck[a1[j]]=0;
                }
            }
 
        }
        for (int j=left;j<=right;j++)
        {
            if (t[j]==1)
            {
                da[a1[j]]=a2[j];
            }
        }
    }
    for (int i=1;i<=q;i++)
    {
        if (t[i]==1)
        {
            continue;
        }
        cout<<ans[i]<<nl;
    }
 
 
}
// goodbye see ya

Compilation message

bridges.cpp:1:1: warning: multi-line comment [-Wcomment]
    1 | //------------------------------------\\
      | ^
bridges.cpp: In function 'void onepunchac168()':
bridges.cpp:204:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  204 |             while (ida<cnt.size()&&cnt[ida].fi>=v.fi)
      |                    ~~~^~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:15:66: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 | #define       file(name)    if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:108:5: note: in expansion of macro 'file'
  108 |     file(task);
      |     ^~~~
bridges.cpp:15:99: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 | #define       file(name)    if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:108:5: note: in expansion of macro 'file'
  108 |     file(task);
      |     ^~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 36 ms 2568 KB Output is correct
4 Correct 18 ms 2396 KB Output is correct
5 Correct 27 ms 2528 KB Output is correct
6 Correct 25 ms 2396 KB Output is correct
7 Correct 25 ms 2396 KB Output is correct
8 Correct 26 ms 2396 KB Output is correct
9 Correct 25 ms 2396 KB Output is correct
10 Correct 27 ms 2536 KB Output is correct
11 Correct 27 ms 2396 KB Output is correct
12 Correct 28 ms 2536 KB Output is correct
13 Correct 35 ms 2396 KB Output is correct
14 Correct 31 ms 2396 KB Output is correct
15 Correct 31 ms 2540 KB Output is correct
16 Correct 25 ms 2396 KB Output is correct
17 Correct 26 ms 2392 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 945 ms 4728 KB Output is correct
2 Correct 971 ms 4716 KB Output is correct
3 Correct 966 ms 4744 KB Output is correct
4 Correct 993 ms 4748 KB Output is correct
5 Correct 1006 ms 4660 KB Output is correct
6 Correct 1245 ms 4628 KB Output is correct
7 Correct 1240 ms 4756 KB Output is correct
8 Correct 1219 ms 4776 KB Output is correct
9 Correct 174 ms 2504 KB Output is correct
10 Correct 954 ms 4760 KB Output is correct
11 Correct 950 ms 4812 KB Output is correct
12 Correct 852 ms 4780 KB Output is correct
13 Correct 737 ms 4812 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 726 ms 3992 KB Output is correct
2 Correct 547 ms 3060 KB Output is correct
3 Correct 787 ms 3740 KB Output is correct
4 Correct 714 ms 3720 KB Output is correct
5 Correct 172 ms 2644 KB Output is correct
6 Correct 747 ms 4076 KB Output is correct
7 Correct 680 ms 3740 KB Output is correct
8 Correct 638 ms 4104 KB Output is correct
9 Correct 612 ms 3848 KB Output is correct
10 Correct 583 ms 3908 KB Output is correct
11 Correct 447 ms 3708 KB Output is correct
12 Correct 426 ms 3944 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1177 ms 6700 KB Output is correct
2 Correct 185 ms 2640 KB Output is correct
3 Correct 129 ms 6324 KB Output is correct
4 Correct 157 ms 6324 KB Output is correct
5 Correct 1321 ms 6572 KB Output is correct
6 Correct 1160 ms 6568 KB Output is correct
7 Correct 1362 ms 6904 KB Output is correct
8 Correct 659 ms 4832 KB Output is correct
9 Correct 656 ms 4892 KB Output is correct
10 Correct 664 ms 4624 KB Output is correct
11 Correct 966 ms 5996 KB Output is correct
12 Correct 930 ms 6008 KB Output is correct
13 Correct 998 ms 5928 KB Output is correct
14 Correct 1298 ms 6840 KB Output is correct
15 Correct 1349 ms 6504 KB Output is correct
16 Correct 1175 ms 6676 KB Output is correct
17 Correct 1213 ms 6640 KB Output is correct
18 Correct 1173 ms 6508 KB Output is correct
19 Correct 1191 ms 6732 KB Output is correct
20 Correct 1057 ms 6524 KB Output is correct
21 Correct 1054 ms 6448 KB Output is correct
22 Correct 1140 ms 6568 KB Output is correct
23 Correct 1133 ms 6396 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 945 ms 4728 KB Output is correct
2 Correct 971 ms 4716 KB Output is correct
3 Correct 966 ms 4744 KB Output is correct
4 Correct 993 ms 4748 KB Output is correct
5 Correct 1006 ms 4660 KB Output is correct
6 Correct 1245 ms 4628 KB Output is correct
7 Correct 1240 ms 4756 KB Output is correct
8 Correct 1219 ms 4776 KB Output is correct
9 Correct 174 ms 2504 KB Output is correct
10 Correct 954 ms 4760 KB Output is correct
11 Correct 950 ms 4812 KB Output is correct
12 Correct 852 ms 4780 KB Output is correct
13 Correct 737 ms 4812 KB Output is correct
14 Correct 726 ms 3992 KB Output is correct
15 Correct 547 ms 3060 KB Output is correct
16 Correct 787 ms 3740 KB Output is correct
17 Correct 714 ms 3720 KB Output is correct
18 Correct 172 ms 2644 KB Output is correct
19 Correct 747 ms 4076 KB Output is correct
20 Correct 680 ms 3740 KB Output is correct
21 Correct 638 ms 4104 KB Output is correct
22 Correct 612 ms 3848 KB Output is correct
23 Correct 583 ms 3908 KB Output is correct
24 Correct 447 ms 3708 KB Output is correct
25 Correct 426 ms 3944 KB Output is correct
26 Correct 898 ms 4808 KB Output is correct
27 Correct 1041 ms 4720 KB Output is correct
28 Correct 947 ms 4620 KB Output is correct
29 Correct 794 ms 4548 KB Output is correct
30 Correct 1039 ms 4740 KB Output is correct
31 Correct 1043 ms 4756 KB Output is correct
32 Correct 1045 ms 4744 KB Output is correct
33 Correct 978 ms 4712 KB Output is correct
34 Correct 975 ms 4776 KB Output is correct
35 Correct 968 ms 4612 KB Output is correct
36 Correct 830 ms 4564 KB Output is correct
37 Correct 832 ms 4564 KB Output is correct
38 Correct 818 ms 4540 KB Output is correct
39 Correct 767 ms 4860 KB Output is correct
40 Correct 748 ms 4616 KB Output is correct
41 Correct 751 ms 4896 KB Output is correct
42 Correct 586 ms 4752 KB Output is correct
43 Correct 586 ms 4564 KB Output is correct
44 Correct 584 ms 4552 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 36 ms 2568 KB Output is correct
4 Correct 18 ms 2396 KB Output is correct
5 Correct 27 ms 2528 KB Output is correct
6 Correct 25 ms 2396 KB Output is correct
7 Correct 25 ms 2396 KB Output is correct
8 Correct 26 ms 2396 KB Output is correct
9 Correct 25 ms 2396 KB Output is correct
10 Correct 27 ms 2536 KB Output is correct
11 Correct 27 ms 2396 KB Output is correct
12 Correct 28 ms 2536 KB Output is correct
13 Correct 35 ms 2396 KB Output is correct
14 Correct 31 ms 2396 KB Output is correct
15 Correct 31 ms 2540 KB Output is correct
16 Correct 25 ms 2396 KB Output is correct
17 Correct 26 ms 2392 KB Output is correct
18 Correct 945 ms 4728 KB Output is correct
19 Correct 971 ms 4716 KB Output is correct
20 Correct 966 ms 4744 KB Output is correct
21 Correct 993 ms 4748 KB Output is correct
22 Correct 1006 ms 4660 KB Output is correct
23 Correct 1245 ms 4628 KB Output is correct
24 Correct 1240 ms 4756 KB Output is correct
25 Correct 1219 ms 4776 KB Output is correct
26 Correct 174 ms 2504 KB Output is correct
27 Correct 954 ms 4760 KB Output is correct
28 Correct 950 ms 4812 KB Output is correct
29 Correct 852 ms 4780 KB Output is correct
30 Correct 737 ms 4812 KB Output is correct
31 Correct 726 ms 3992 KB Output is correct
32 Correct 547 ms 3060 KB Output is correct
33 Correct 787 ms 3740 KB Output is correct
34 Correct 714 ms 3720 KB Output is correct
35 Correct 172 ms 2644 KB Output is correct
36 Correct 747 ms 4076 KB Output is correct
37 Correct 680 ms 3740 KB Output is correct
38 Correct 638 ms 4104 KB Output is correct
39 Correct 612 ms 3848 KB Output is correct
40 Correct 583 ms 3908 KB Output is correct
41 Correct 447 ms 3708 KB Output is correct
42 Correct 426 ms 3944 KB Output is correct
43 Correct 1177 ms 6700 KB Output is correct
44 Correct 185 ms 2640 KB Output is correct
45 Correct 129 ms 6324 KB Output is correct
46 Correct 157 ms 6324 KB Output is correct
47 Correct 1321 ms 6572 KB Output is correct
48 Correct 1160 ms 6568 KB Output is correct
49 Correct 1362 ms 6904 KB Output is correct
50 Correct 659 ms 4832 KB Output is correct
51 Correct 656 ms 4892 KB Output is correct
52 Correct 664 ms 4624 KB Output is correct
53 Correct 966 ms 5996 KB Output is correct
54 Correct 930 ms 6008 KB Output is correct
55 Correct 998 ms 5928 KB Output is correct
56 Correct 1298 ms 6840 KB Output is correct
57 Correct 1349 ms 6504 KB Output is correct
58 Correct 1175 ms 6676 KB Output is correct
59 Correct 1213 ms 6640 KB Output is correct
60 Correct 1173 ms 6508 KB Output is correct
61 Correct 1191 ms 6732 KB Output is correct
62 Correct 1057 ms 6524 KB Output is correct
63 Correct 1054 ms 6448 KB Output is correct
64 Correct 1140 ms 6568 KB Output is correct
65 Correct 1133 ms 6396 KB Output is correct
66 Correct 898 ms 4808 KB Output is correct
67 Correct 1041 ms 4720 KB Output is correct
68 Correct 947 ms 4620 KB Output is correct
69 Correct 794 ms 4548 KB Output is correct
70 Correct 1039 ms 4740 KB Output is correct
71 Correct 1043 ms 4756 KB Output is correct
72 Correct 1045 ms 4744 KB Output is correct
73 Correct 978 ms 4712 KB Output is correct
74 Correct 975 ms 4776 KB Output is correct
75 Correct 968 ms 4612 KB Output is correct
76 Correct 830 ms 4564 KB Output is correct
77 Correct 832 ms 4564 KB Output is correct
78 Correct 818 ms 4540 KB Output is correct
79 Correct 767 ms 4860 KB Output is correct
80 Correct 748 ms 4616 KB Output is correct
81 Correct 751 ms 4896 KB Output is correct
82 Correct 586 ms 4752 KB Output is correct
83 Correct 586 ms 4564 KB Output is correct
84 Correct 584 ms 4552 KB Output is correct
85 Correct 1435 ms 6800 KB Output is correct
86 Correct 149 ms 6316 KB Output is correct
87 Correct 187 ms 6308 KB Output is correct
88 Correct 1596 ms 6972 KB Output is correct
89 Correct 1459 ms 6904 KB Output is correct
90 Correct 1573 ms 6484 KB Output is correct
91 Correct 995 ms 4752 KB Output is correct
92 Correct 1012 ms 4740 KB Output is correct
93 Correct 1170 ms 4688 KB Output is correct
94 Correct 1250 ms 6024 KB Output is correct
95 Correct 1248 ms 5996 KB Output is correct
96 Correct 1328 ms 5920 KB Output is correct
97 Correct 1472 ms 6580 KB Output is correct
98 Correct 1288 ms 6948 KB Output is correct
99 Correct 1455 ms 6936 KB Output is correct
100 Correct 1470 ms 6516 KB Output is correct
101 Correct 1466 ms 7000 KB Output is correct
102 Correct 1466 ms 6772 KB Output is correct
103 Correct 1412 ms 6412 KB Output is correct
104 Correct 1402 ms 6588 KB Output is correct
105 Correct 1051 ms 6388 KB Output is correct
106 Correct 891 ms 5964 KB Output is correct
107 Correct 1214 ms 6576 KB Output is correct
108 Correct 1473 ms 6688 KB Output is correct
109 Correct 1467 ms 6200 KB Output is correct