oj.uz

Submission #486400

# Submission time Handle Problem Language Result Execution time Memory
486400 2021-11-11T14:59:55 Z urosk Bridges (APIO19_bridges) C++14
100 / 100
 2035 ms 32328 KB 
//https://usaco.guide/problems/apio-2019bridges/solution
// __builtin_popcount(x) broj bitova
// __builtin_popcountll(x)
// __builtin_clz(x) vodece nule
// __builtin_clzll(x)
// __builtin_ctz(x) nule na pocetku
// __builtin_ctzll(x)
// 2000000011
// 2000000033
#include "bits/stdc++.h"
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll int
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define rall(a) a.begin(),a.end(),greater<int>()
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}
#define pi 3.14159265358979323846
#define here cerr<<"---------------------------\n"
#define ceri(a,l,r) {for(ll i = l;i<=r;i++) cerr<<a[i]<< " ";cerr<<endl;}
#define ceri2(a,l,r,n,m) {for(ll i = l;i<=r;i++){for(ll j = n;j<=m;j++) cerr<<a[i][j]<< " ";cerr<<endl;}}
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
    return uniform_int_distribution<ll>(l,r)(rng);
}

void setIO(string inoutname)
{
	freopen((inoutname+".in").c_str(),"r",stdin);
    	freopen((inoutname+".out").c_str(),"w",stdout);
}
#define mod 1
ll gcd(ll a, ll b)
{
   if(b==0) return a;
   if(a==0) return b;
   if(a>=b)  return gcd(a%b,b);
   return  gcd(a,b%a);
}
ll lcm(ll a,ll b){
   return (a/gcd(a,b))*b;
}
ll add(ll a,ll b){
	a+=b;
	a+=mod;
	if(a>=mod) a%=mod;
	return a;
}
ll mul(ll a,ll b){return(a*b)%mod;}
#define maxn 100005
#define maxd 1005
ll n,m,q;
ll u[maxn],v[maxn],w[maxn];
ll tip[maxn],x[maxn],y[maxn];
ll dsu[maxn];
bool menja[maxn];
ll ans[maxn];
vector<ll> join[maxd];
ll siz[maxn];
stack<ll> s;
ll d = 1;
ll root(ll u){while(u!=dsu[u]) u = dsu[u];return u;}
void upd(ll x,ll y){
    x = root(x);
    y = root(y);
    if(x==y) return;
    if(siz[x]>siz[y]) swap(x,y);
    s.push(x);
    dsu[x] = y;
    siz[y]+=siz[x];
}
void roluj(ll x){
    while(sz(s)>x){
        ll u = s.top();
        ll v = dsu[u];
        siz[v]-=siz[u];
        dsu[u] = u;
        s.pop();
    }
}

void tc(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n >> m;
    for(ll i = 1;i<=m;i++) cin >> u[i] >> v[i] >> w[i];
    cin >> q;
    d = 1000;
    for(ll i = 1;i<=q;i++) cin >> tip[i] >> x[i] >> y[i];
    for(ll l = 1;l<=q;l+=d){
        ll r = min(q,l+d-1);
        fill(siz+1,siz+n+1,1);
        iota(dsu+1,dsu+n+1,1);
        fill(menja,menja+m+1,0);
        vector<ll> up,ask,p;
        for(ll i = l;i<=r;i++){
            if(tip[i]==1){
                menja[x[i]] = 1;
                up.pb(i);
            }else ask.pb(i);
        }
        for(ll i = 1;i<=m;i++) if(!menja[i]) p.pb(i);
        for(ll i = l;i<=r;i++){
            if(tip[i]==1){
                w[x[i]] = y[i];
            }else{
                join[i-l].clear();
                for(ll j : up) if(w[x[j]]>=y[i]) join[i-l].pb(x[j]);
            }
        }
        sort(all(ask),[&](ll a,ll b){return y[a]>y[b];});
        sort(all(p),[&](ll a,ll b){return w[a]>w[b];});
        ll it = 0;
        for(ll i : ask){
            while(it<sz(p)&&w[p[it]]>=y[i]){
                upd(u[p[it]],v[p[it]]);
                it++;
            }
            ll sizi = sz(s);
            for(ll j : join[i-l]) upd(u[j],v[j]);
            ans[i] = siz[root(x[i])];
            roluj(sizi);
        }
    }
    for(ll i = 1;i<=q;i++) if(tip[i]==2) cout<<ans[i]<<endl;
}
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
	//setIO("lol");
	int t; t = 1;
	while(t--){
		tc();
	}
	return 0;
}

Compilation message

bridges.cpp: In function 'void setIO(std::string)':
bridges.cpp:48:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  freopen((inoutname+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:49:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |      freopen((inoutname+".out").c_str(),"w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 33 ms 2628 KB Output is correct
4 Correct 3 ms 528 KB Output is correct
5 Correct 34 ms 2868 KB Output is correct
6 Correct 26 ms 2532 KB Output is correct
7 Correct 31 ms 3452 KB Output is correct
8 Correct 34 ms 2592 KB Output is correct
9 Correct 40 ms 4228 KB Output is correct
10 Correct 35 ms 2752 KB Output is correct
11 Correct 34 ms 2636 KB Output is correct
12 Correct 42 ms 2828 KB Output is correct
13 Correct 41 ms 2756 KB Output is correct
14 Correct 37 ms 2632 KB Output is correct
15 Correct 40 ms 2576 KB Output is correct
16 Correct 37 ms 3948 KB Output is correct
17 Correct 36 ms 3324 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1187 ms 26300 KB Output is correct
2 Correct 1244 ms 26076 KB Output is correct
3 Correct 1186 ms 26156 KB Output is correct
4 Correct 1237 ms 26064 KB Output is correct
5 Correct 1215 ms 26356 KB Output is correct
6 Correct 1886 ms 27944 KB Output is correct
7 Correct 1905 ms 27844 KB Output is correct
8 Correct 2035 ms 27884 KB Output is correct
9 Correct 44 ms 2076 KB Output is correct
10 Correct 1164 ms 27916 KB Output is correct
11 Correct 1062 ms 27908 KB Output is correct
12 Correct 1065 ms 24624 KB Output is correct
13 Correct 1125 ms 27448 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1038 ms 18624 KB Output is correct
2 Correct 805 ms 9608 KB Output is correct
3 Correct 1250 ms 20536 KB Output is correct
4 Correct 977 ms 18772 KB Output is correct
5 Correct 31 ms 2116 KB Output is correct
6 Correct 1123 ms 18816 KB Output is correct
7 Correct 872 ms 18356 KB Output is correct
8 Correct 761 ms 18356 KB Output is correct
9 Correct 648 ms 17124 KB Output is correct
10 Correct 551 ms 16932 KB Output is correct
11 Correct 666 ms 19764 KB Output is correct
12 Correct 577 ms 19804 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1375 ms 24936 KB Output is correct
2 Correct 31 ms 3400 KB Output is correct
3 Correct 139 ms 4532 KB Output is correct
4 Correct 66 ms 4636 KB Output is correct
5 Correct 684 ms 27124 KB Output is correct
6 Correct 1306 ms 28800 KB Output is correct
7 Correct 658 ms 27280 KB Output is correct
8 Correct 636 ms 26516 KB Output is correct
9 Correct 653 ms 26716 KB Output is correct
10 Correct 658 ms 26704 KB Output is correct
11 Correct 1008 ms 27888 KB Output is correct
12 Correct 994 ms 28136 KB Output is correct
13 Correct 1025 ms 28104 KB Output is correct
14 Correct 596 ms 27268 KB Output is correct
15 Correct 627 ms 27288 KB Output is correct
16 Correct 1351 ms 28892 KB Output is correct
17 Correct 1371 ms 28860 KB Output is correct
18 Correct 1400 ms 29144 KB Output is correct
19 Correct 1418 ms 29184 KB Output is correct
20 Correct 1220 ms 28284 KB Output is correct
21 Correct 1196 ms 28304 KB Output is correct
22 Correct 1321 ms 28476 KB Output is correct
23 Correct 793 ms 25024 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1187 ms 26300 KB Output is correct
2 Correct 1244 ms 26076 KB Output is correct
3 Correct 1186 ms 26156 KB Output is correct
4 Correct 1237 ms 26064 KB Output is correct
5 Correct 1215 ms 26356 KB Output is correct
6 Correct 1886 ms 27944 KB Output is correct
7 Correct 1905 ms 27844 KB Output is correct
8 Correct 2035 ms 27884 KB Output is correct
9 Correct 44 ms 2076 KB Output is correct
10 Correct 1164 ms 27916 KB Output is correct
11 Correct 1062 ms 27908 KB Output is correct
12 Correct 1065 ms 24624 KB Output is correct
13 Correct 1125 ms 27448 KB Output is correct
14 Correct 1038 ms 18624 KB Output is correct
15 Correct 805 ms 9608 KB Output is correct
16 Correct 1250 ms 20536 KB Output is correct
17 Correct 977 ms 18772 KB Output is correct
18 Correct 31 ms 2116 KB Output is correct
19 Correct 1123 ms 18816 KB Output is correct
20 Correct 872 ms 18356 KB Output is correct
21 Correct 761 ms 18356 KB Output is correct
22 Correct 648 ms 17124 KB Output is correct
23 Correct 551 ms 16932 KB Output is correct
24 Correct 666 ms 19764 KB Output is correct
25 Correct 577 ms 19804 KB Output is correct
26 Correct 1306 ms 26500 KB Output is correct
27 Correct 1564 ms 28288 KB Output is correct
28 Correct 1252 ms 26404 KB Output is correct
29 Correct 891 ms 25948 KB Output is correct
30 Correct 1458 ms 28140 KB Output is correct
31 Correct 1514 ms 28196 KB Output is correct
32 Correct 1488 ms 28152 KB Output is correct
33 Correct 1249 ms 26272 KB Output is correct
34 Correct 1240 ms 26296 KB Output is correct
35 Correct 1237 ms 26504 KB Output is correct
36 Correct 928 ms 26024 KB Output is correct
37 Correct 928 ms 25940 KB Output is correct
38 Correct 935 ms 26024 KB Output is correct
39 Correct 739 ms 24712 KB Output is correct
40 Correct 747 ms 24592 KB Output is correct
41 Correct 744 ms 24584 KB Output is correct
42 Correct 732 ms 26632 KB Output is correct
43 Correct 744 ms 26548 KB Output is correct
44 Correct 733 ms 26612 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 33 ms 2628 KB Output is correct
4 Correct 3 ms 528 KB Output is correct
5 Correct 34 ms 2868 KB Output is correct
6 Correct 26 ms 2532 KB Output is correct
7 Correct 31 ms 3452 KB Output is correct
8 Correct 34 ms 2592 KB Output is correct
9 Correct 40 ms 4228 KB Output is correct
10 Correct 35 ms 2752 KB Output is correct
11 Correct 34 ms 2636 KB Output is correct
12 Correct 42 ms 2828 KB Output is correct
13 Correct 41 ms 2756 KB Output is correct
14 Correct 37 ms 2632 KB Output is correct
15 Correct 40 ms 2576 KB Output is correct
16 Correct 37 ms 3948 KB Output is correct
17 Correct 36 ms 3324 KB Output is correct
18 Correct 1187 ms 26300 KB Output is correct
19 Correct 1244 ms 26076 KB Output is correct
20 Correct 1186 ms 26156 KB Output is correct
21 Correct 1237 ms 26064 KB Output is correct
22 Correct 1215 ms 26356 KB Output is correct
23 Correct 1886 ms 27944 KB Output is correct
24 Correct 1905 ms 27844 KB Output is correct
25 Correct 2035 ms 27884 KB Output is correct
26 Correct 44 ms 2076 KB Output is correct
27 Correct 1164 ms 27916 KB Output is correct
28 Correct 1062 ms 27908 KB Output is correct
29 Correct 1065 ms 24624 KB Output is correct
30 Correct 1125 ms 27448 KB Output is correct
31 Correct 1038 ms 18624 KB Output is correct
32 Correct 805 ms 9608 KB Output is correct
33 Correct 1250 ms 20536 KB Output is correct
34 Correct 977 ms 18772 KB Output is correct
35 Correct 31 ms 2116 KB Output is correct
36 Correct 1123 ms 18816 KB Output is correct
37 Correct 872 ms 18356 KB Output is correct
38 Correct 761 ms 18356 KB Output is correct
39 Correct 648 ms 17124 KB Output is correct
40 Correct 551 ms 16932 KB Output is correct
41 Correct 666 ms 19764 KB Output is correct
42 Correct 577 ms 19804 KB Output is correct
43 Correct 1375 ms 24936 KB Output is correct
44 Correct 31 ms 3400 KB Output is correct
45 Correct 139 ms 4532 KB Output is correct
46 Correct 66 ms 4636 KB Output is correct
47 Correct 684 ms 27124 KB Output is correct
48 Correct 1306 ms 28800 KB Output is correct
49 Correct 658 ms 27280 KB Output is correct
50 Correct 636 ms 26516 KB Output is correct
51 Correct 653 ms 26716 KB Output is correct
52 Correct 658 ms 26704 KB Output is correct
53 Correct 1008 ms 27888 KB Output is correct
54 Correct 994 ms 28136 KB Output is correct
55 Correct 1025 ms 28104 KB Output is correct
56 Correct 596 ms 27268 KB Output is correct
57 Correct 627 ms 27288 KB Output is correct
58 Correct 1351 ms 28892 KB Output is correct
59 Correct 1371 ms 28860 KB Output is correct
60 Correct 1400 ms 29144 KB Output is correct
61 Correct 1418 ms 29184 KB Output is correct
62 Correct 1220 ms 28284 KB Output is correct
63 Correct 1196 ms 28304 KB Output is correct
64 Correct 1321 ms 28476 KB Output is correct
65 Correct 793 ms 25024 KB Output is correct
66 Correct 1306 ms 26500 KB Output is correct
67 Correct 1564 ms 28288 KB Output is correct
68 Correct 1252 ms 26404 KB Output is correct
69 Correct 891 ms 25948 KB Output is correct
70 Correct 1458 ms 28140 KB Output is correct
71 Correct 1514 ms 28196 KB Output is correct
72 Correct 1488 ms 28152 KB Output is correct
73 Correct 1249 ms 26272 KB Output is correct
74 Correct 1240 ms 26296 KB Output is correct
75 Correct 1237 ms 26504 KB Output is correct
76 Correct 928 ms 26024 KB Output is correct
77 Correct 928 ms 25940 KB Output is correct
78 Correct 935 ms 26024 KB Output is correct
79 Correct 739 ms 24712 KB Output is correct
80 Correct 747 ms 24592 KB Output is correct
81 Correct 744 ms 24584 KB Output is correct
82 Correct 732 ms 26632 KB Output is correct
83 Correct 744 ms 26548 KB Output is correct
84 Correct 733 ms 26612 KB Output is correct
85 Correct 1782 ms 31056 KB Output is correct
86 Correct 176 ms 6608 KB Output is correct
87 Correct 108 ms 7996 KB Output is correct
88 Correct 1072 ms 31196 KB Output is correct
89 Correct 1762 ms 31104 KB Output is correct
90 Correct 1048 ms 31200 KB Output is correct
91 Correct 1277 ms 28828 KB Output is correct
92 Correct 1266 ms 28860 KB Output is correct
93 Correct 1873 ms 30352 KB Output is correct
94 Correct 1493 ms 30432 KB Output is correct
95 Correct 1469 ms 30544 KB Output is correct
96 Correct 1762 ms 31864 KB Output is correct
97 Correct 794 ms 27736 KB Output is correct
98 Correct 855 ms 30848 KB Output is correct
99 Correct 1760 ms 31264 KB Output is correct
100 Correct 1756 ms 31008 KB Output is correct
101 Correct 1821 ms 31400 KB Output is correct
102 Correct 1765 ms 31432 KB Output is correct
103 Correct 1926 ms 32156 KB Output is correct
104 Correct 1919 ms 32328 KB Output is correct
105 Correct 1435 ms 32012 KB Output is correct
106 Correct 1174 ms 31724 KB Output is correct
107 Correct 1318 ms 28828 KB Output is correct
108 Correct 1801 ms 31080 KB Output is correct
109 Correct 1253 ms 29032 KB Output is correct