oj.uz

Submission #861961

# Submission time Handle Problem Language Result Execution time Memory
861961 2023-10-17T09:21:52 Z onepunchac168 Bridges (APIO19_bridges) C++14
100 / 100
 1973 ms 10804 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=700;
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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 28 ms 2564 KB Output is correct
4 Correct 13 ms 2392 KB Output is correct
5 Correct 22 ms 2396 KB Output is correct
6 Correct 21 ms 2524 KB Output is correct
7 Correct 21 ms 2396 KB Output is correct
8 Correct 21 ms 2392 KB Output is correct
9 Correct 30 ms 2396 KB Output is correct
10 Correct 22 ms 2536 KB Output is correct
11 Correct 22 ms 2536 KB Output is correct
12 Correct 32 ms 2532 KB Output is correct
13 Correct 30 ms 2516 KB Output is correct
14 Correct 26 ms 2556 KB Output is correct
15 Correct 26 ms 2396 KB Output is correct
16 Correct 29 ms 2540 KB Output is correct
17 Correct 24 ms 2396 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1025 ms 4812 KB Output is correct
2 Correct 1044 ms 4604 KB Output is correct
3 Correct 1039 ms 4648 KB Output is correct
4 Correct 1075 ms 4748 KB Output is correct
5 Correct 1076 ms 4788 KB Output is correct
6 Correct 1179 ms 4816 KB Output is correct
7 Correct 1196 ms 4864 KB Output is correct
8 Correct 1200 ms 4720 KB Output is correct
9 Correct 130 ms 2508 KB Output is correct
10 Correct 1014 ms 4712 KB Output is correct
11 Correct 1014 ms 4804 KB Output is correct
12 Correct 940 ms 4820 KB Output is correct
13 Correct 861 ms 4932 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 741 ms 3968 KB Output is correct
2 Correct 443 ms 2780 KB Output is correct
3 Correct 779 ms 3852 KB Output is correct
4 Correct 738 ms 4308 KB Output is correct
5 Correct 131 ms 2640 KB Output is correct
6 Correct 753 ms 4064 KB Output is correct
7 Correct 705 ms 3984 KB Output is correct
8 Correct 675 ms 4248 KB Output is correct
9 Correct 656 ms 4296 KB Output is correct
10 Correct 627 ms 3728 KB Output is correct
11 Correct 520 ms 3716 KB Output is correct
12 Correct 504 ms 3932 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1539 ms 6768 KB Output is correct
2 Correct 129 ms 3868 KB Output is correct
3 Correct 160 ms 8192 KB Output is correct
4 Correct 196 ms 8264 KB Output is correct
5 Correct 1756 ms 9044 KB Output is correct
6 Correct 1510 ms 10500 KB Output is correct
7 Correct 1814 ms 8992 KB Output is correct
8 Correct 810 ms 7248 KB Output is correct
9 Correct 802 ms 7376 KB Output is correct
10 Correct 822 ms 7240 KB Output is correct
11 Correct 1242 ms 9292 KB Output is correct
12 Correct 1200 ms 9568 KB Output is correct
13 Correct 1254 ms 9064 KB Output is correct
14 Correct 1718 ms 8776 KB Output is correct
15 Correct 1791 ms 8848 KB Output is correct
16 Correct 1549 ms 10436 KB Output is correct
17 Correct 1600 ms 10432 KB Output is correct
18 Correct 1532 ms 10556 KB Output is correct
19 Correct 1566 ms 10524 KB Output is correct
20 Correct 1361 ms 9472 KB Output is correct
21 Correct 1362 ms 9888 KB Output is correct
22 Correct 1490 ms 9996 KB Output is correct
23 Correct 1490 ms 8148 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1025 ms 4812 KB Output is correct
2 Correct 1044 ms 4604 KB Output is correct
3 Correct 1039 ms 4648 KB Output is correct
4 Correct 1075 ms 4748 KB Output is correct
5 Correct 1076 ms 4788 KB Output is correct
6 Correct 1179 ms 4816 KB Output is correct
7 Correct 1196 ms 4864 KB Output is correct
8 Correct 1200 ms 4720 KB Output is correct
9 Correct 130 ms 2508 KB Output is correct
10 Correct 1014 ms 4712 KB Output is correct
11 Correct 1014 ms 4804 KB Output is correct
12 Correct 940 ms 4820 KB Output is correct
13 Correct 861 ms 4932 KB Output is correct
14 Correct 741 ms 3968 KB Output is correct
15 Correct 443 ms 2780 KB Output is correct
16 Correct 779 ms 3852 KB Output is correct
17 Correct 738 ms 4308 KB Output is correct
18 Correct 131 ms 2640 KB Output is correct
19 Correct 753 ms 4064 KB Output is correct
20 Correct 705 ms 3984 KB Output is correct
21 Correct 675 ms 4248 KB Output is correct
22 Correct 656 ms 4296 KB Output is correct
23 Correct 627 ms 3728 KB Output is correct
24 Correct 520 ms 3716 KB Output is correct
25 Correct 504 ms 3932 KB Output is correct
26 Correct 981 ms 4752 KB Output is correct
27 Correct 1096 ms 4828 KB Output is correct
28 Correct 1040 ms 4624 KB Output is correct
29 Correct 916 ms 4768 KB Output is correct
30 Correct 1098 ms 4824 KB Output is correct
31 Correct 1126 ms 4584 KB Output is correct
32 Correct 1104 ms 4648 KB Output is correct
33 Correct 1043 ms 4624 KB Output is correct
34 Correct 1057 ms 4748 KB Output is correct
35 Correct 1050 ms 4648 KB Output is correct
36 Correct 946 ms 4876 KB Output is correct
37 Correct 942 ms 4820 KB Output is correct
38 Correct 937 ms 4688 KB Output is correct
39 Correct 890 ms 4700 KB Output is correct
40 Correct 890 ms 4824 KB Output is correct
41 Correct 883 ms 4632 KB Output is correct
42 Correct 755 ms 4544 KB Output is correct
43 Correct 765 ms 4692 KB Output is correct
44 Correct 754 ms 4556 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 28 ms 2564 KB Output is correct
4 Correct 13 ms 2392 KB Output is correct
5 Correct 22 ms 2396 KB Output is correct
6 Correct 21 ms 2524 KB Output is correct
7 Correct 21 ms 2396 KB Output is correct
8 Correct 21 ms 2392 KB Output is correct
9 Correct 30 ms 2396 KB Output is correct
10 Correct 22 ms 2536 KB Output is correct
11 Correct 22 ms 2536 KB Output is correct
12 Correct 32 ms 2532 KB Output is correct
13 Correct 30 ms 2516 KB Output is correct
14 Correct 26 ms 2556 KB Output is correct
15 Correct 26 ms 2396 KB Output is correct
16 Correct 29 ms 2540 KB Output is correct
17 Correct 24 ms 2396 KB Output is correct
18 Correct 1025 ms 4812 KB Output is correct
19 Correct 1044 ms 4604 KB Output is correct
20 Correct 1039 ms 4648 KB Output is correct
21 Correct 1075 ms 4748 KB Output is correct
22 Correct 1076 ms 4788 KB Output is correct
23 Correct 1179 ms 4816 KB Output is correct
24 Correct 1196 ms 4864 KB Output is correct
25 Correct 1200 ms 4720 KB Output is correct
26 Correct 130 ms 2508 KB Output is correct
27 Correct 1014 ms 4712 KB Output is correct
28 Correct 1014 ms 4804 KB Output is correct
29 Correct 940 ms 4820 KB Output is correct
30 Correct 861 ms 4932 KB Output is correct
31 Correct 741 ms 3968 KB Output is correct
32 Correct 443 ms 2780 KB Output is correct
33 Correct 779 ms 3852 KB Output is correct
34 Correct 738 ms 4308 KB Output is correct
35 Correct 131 ms 2640 KB Output is correct
36 Correct 753 ms 4064 KB Output is correct
37 Correct 705 ms 3984 KB Output is correct
38 Correct 675 ms 4248 KB Output is correct
39 Correct 656 ms 4296 KB Output is correct
40 Correct 627 ms 3728 KB Output is correct
41 Correct 520 ms 3716 KB Output is correct
42 Correct 504 ms 3932 KB Output is correct
43 Correct 1539 ms 6768 KB Output is correct
44 Correct 129 ms 3868 KB Output is correct
45 Correct 160 ms 8192 KB Output is correct
46 Correct 196 ms 8264 KB Output is correct
47 Correct 1756 ms 9044 KB Output is correct
48 Correct 1510 ms 10500 KB Output is correct
49 Correct 1814 ms 8992 KB Output is correct
50 Correct 810 ms 7248 KB Output is correct
51 Correct 802 ms 7376 KB Output is correct
52 Correct 822 ms 7240 KB Output is correct
53 Correct 1242 ms 9292 KB Output is correct
54 Correct 1200 ms 9568 KB Output is correct
55 Correct 1254 ms 9064 KB Output is correct
56 Correct 1718 ms 8776 KB Output is correct
57 Correct 1791 ms 8848 KB Output is correct
58 Correct 1549 ms 10436 KB Output is correct
59 Correct 1600 ms 10432 KB Output is correct
60 Correct 1532 ms 10556 KB Output is correct
61 Correct 1566 ms 10524 KB Output is correct
62 Correct 1361 ms 9472 KB Output is correct
63 Correct 1362 ms 9888 KB Output is correct
64 Correct 1490 ms 9996 KB Output is correct
65 Correct 1490 ms 8148 KB Output is correct
66 Correct 981 ms 4752 KB Output is correct
67 Correct 1096 ms 4828 KB Output is correct
68 Correct 1040 ms 4624 KB Output is correct
69 Correct 916 ms 4768 KB Output is correct
70 Correct 1098 ms 4824 KB Output is correct
71 Correct 1126 ms 4584 KB Output is correct
72 Correct 1104 ms 4648 KB Output is correct
73 Correct 1043 ms 4624 KB Output is correct
74 Correct 1057 ms 4748 KB Output is correct
75 Correct 1050 ms 4648 KB Output is correct
76 Correct 946 ms 4876 KB Output is correct
77 Correct 942 ms 4820 KB Output is correct
78 Correct 937 ms 4688 KB Output is correct
79 Correct 890 ms 4700 KB Output is correct
80 Correct 890 ms 4824 KB Output is correct
81 Correct 883 ms 4632 KB Output is correct
82 Correct 755 ms 4544 KB Output is correct
83 Correct 765 ms 4692 KB Output is correct
84 Correct 754 ms 4556 KB Output is correct
85 Correct 1728 ms 10548 KB Output is correct
86 Correct 176 ms 8180 KB Output is correct
87 Correct 224 ms 8508 KB Output is correct
88 Correct 1973 ms 9236 KB Output is correct
89 Correct 1736 ms 10596 KB Output is correct
90 Correct 1943 ms 8780 KB Output is correct
91 Correct 1083 ms 7436 KB Output is correct
92 Correct 1060 ms 7416 KB Output is correct
93 Correct 1171 ms 7380 KB Output is correct
94 Correct 1470 ms 9164 KB Output is correct
95 Correct 1466 ms 9440 KB Output is correct
96 Correct 1511 ms 9292 KB Output is correct
97 Correct 1855 ms 8868 KB Output is correct
98 Correct 1730 ms 9064 KB Output is correct
99 Correct 1775 ms 10224 KB Output is correct
100 Correct 1784 ms 10612 KB Output is correct
101 Correct 1767 ms 10804 KB Output is correct
102 Correct 1787 ms 10588 KB Output is correct
103 Correct 1627 ms 10164 KB Output is correct
104 Correct 1624 ms 9716 KB Output is correct
105 Correct 1377 ms 9480 KB Output is correct
106 Correct 1182 ms 9312 KB Output is correct
107 Correct 1493 ms 9404 KB Output is correct
108 Correct 1751 ms 10212 KB Output is correct
109 Correct 1742 ms 8136 KB Output is correct