# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
290279 |
2020-09-03T15:13:01 Z |
NaimSS |
Bridges (APIO19_bridges) |
C++14 |
|
3000 ms |
11296 KB |
#include <bits/stdc++.h>
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define Unique(v) sort(all(v));v.erase(unique(all(v)),v.end());
#define sz(v) (int)v.size()
//#define int long long
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
#define left sefude
#define db(x) cerr << #x <<" == "<<x << endl;
#define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl;
#define db3(x,y,z) cerr << #x<<" == "<<x<<", "<<#y<<" == "<<y<<", "<<#z<<" == "<<z<<endl;
typedef long long ll;
typedef pair<int,int> pii;
inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll a,ll b,ll m){
if(b==0LL) return 1LL;
if(b==1LL) return mod(a,m);
ll k = mod(exp(a,b/2,m),m);
if(b&1LL){
return mod(a*mod(k*k,m),m);
}
else return mod(k*k,m);
}
struct DSU{
vi pai,ps;
DSU(){}
DSU(int n){
pai.resize(n+1);
ps.resize(n+1);
for(int i=1;i<=n;i++)pai[i]=i,ps[i]=1;
}
int f(int x){
return pai[x] = (pai[x]==x?x:f(pai[x]));
}
int getsz(int x){
return ps[f(x)];
}
void join(int a,int b){
a=f(a),b=f(b);
if(a==b)return;
if(ps[a]>ps[b]){int c=a;a=b,b=c;}
ps[b]+=ps[a];
pai[a]=b;
}
};
const int N = 50100,M = 100100;
const int sq = 400;
vi g[N]; // guarda os ids
int a[M],b[M],c[M];
int res[M];
int vis[N];
int T=0;
int t[M],s[M],w[M];
int m,n;
vector<int> ar[N];
bool jf[M];
DSU dsu(0);
int dfs(int v){
vis[v] = T;
int r = dsu.getsz(v);
for(int to : ar[v])if(vis[to]!=T){
r+=dfs(to);
}
return r;
}
bool used[M];
vi edge;
// O(N*sq^2 + MlogM * M/sq + Q*sq + )
void go(vi qry){
vi Q,upd;
for(int id : qry){
if(t[id] == 2)Q.pb(id);
else{
upd.pb(id);
used[s[id]] = 1;
}
}
vi unused;
for(int i=1;i<=m;i++){ // O(M)
if(used[i]){
unused.pb(i);
continue;
}
}
sort(all(Q),[&](int a,int b){
return w[a] > w[b];
}); // sqrt * log(sqrt);
dsu = DSU(n); // O(N * alpha)
reverse(all(upd));
int curedge = 0;
for(int id : Q){
while(curedge < sz(edge) and c[edge[curedge]]>=w[id]){ // O(M)
// gogo
int ed = edge[curedge];
if(used[ed]){
curedge++;
continue;
}
dsu.join(a[ed],b[ed]);
curedge++;
}
T++;
for(int id2 : upd){
if(id2 > id || jf[s[id2]])continue;
jf[s[id2]] = 1;
if(w[id2] >= w[id]){
// add edge:
int ed = s[id2];
ar[dsu.f(a[ed])].pb(dsu.f(b[ed]));
ar[dsu.f(b[ed])].pb(dsu.f(a[ed]));
}
}
for(int id2 : unused){
if(!jf[id2] and c[id2] >= w[id]){
ar[dsu.f(a[id2])].pb(dsu.f(b[id2]));
ar[dsu.f(b[id2])].pb(dsu.f(a[id2]));
jf[id2] = 1;
}
}
res[id] = dfs(dsu.f(s[id]));
// rool back
for(int id2 : upd){
jf[s[id2]] = 0;
int ed = s[id2];
ar[dsu.f(a[ed])].clear();
ar[dsu.f(b[ed])].clear();
}
for(int id2 : unused){
jf[id2] = 0;
ar[dsu.f(a[id2])].clear();
ar[dsu.f(b[id2])].clear();
}
}
for(int ed : unused){
used[ed] = 0;
}
// update the edges:
for(int id : qry){
if(t[id] == 1){
c[s[id]] = w[id];
}
}
sort(all(edge),[&](int a,int b){
return c[a] > c[b];
});
}
int32_t main(){
fastio;
cin>>n>>m;
for(int i=1;i<=m;i++){
cin >> a[i] >> b[i] >> c[i];
edge.pb(i);
}
sort(all(edge),[&](int a,int b){
return c[a] > c[b];
});
int q;
cin >> q;
vi qry;
for(int i=0;i<q;i++){
cin >> t[i] >> s[i] >> w[i];
qry.pb(i);
if(sz(qry) == sq){
go(qry);
qry.clear();
}
}
go(qry);
for(int i=0;i<q;i++){
if(t[i] == 2)cout << res[i] << endl;
}
// math -> gcd it all
// Did u check N=1? Did you switch N,M?
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
Output is correct |
2 |
Correct |
2 ms |
2688 KB |
Output is correct |
3 |
Correct |
70 ms |
2936 KB |
Output is correct |
4 |
Correct |
6 ms |
2944 KB |
Output is correct |
5 |
Correct |
44 ms |
3064 KB |
Output is correct |
6 |
Correct |
42 ms |
2936 KB |
Output is correct |
7 |
Correct |
42 ms |
2936 KB |
Output is correct |
8 |
Correct |
39 ms |
2936 KB |
Output is correct |
9 |
Correct |
48 ms |
2936 KB |
Output is correct |
10 |
Correct |
39 ms |
2936 KB |
Output is correct |
11 |
Correct |
38 ms |
2936 KB |
Output is correct |
12 |
Correct |
40 ms |
2936 KB |
Output is correct |
13 |
Correct |
48 ms |
2936 KB |
Output is correct |
14 |
Correct |
46 ms |
2936 KB |
Output is correct |
15 |
Correct |
47 ms |
2928 KB |
Output is correct |
16 |
Correct |
43 ms |
2936 KB |
Output is correct |
17 |
Correct |
42 ms |
2936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2515 ms |
8068 KB |
Output is correct |
2 |
Correct |
2452 ms |
10900 KB |
Output is correct |
3 |
Correct |
2439 ms |
10732 KB |
Output is correct |
4 |
Correct |
2460 ms |
10796 KB |
Output is correct |
5 |
Correct |
2405 ms |
11016 KB |
Output is correct |
6 |
Correct |
2847 ms |
9640 KB |
Output is correct |
7 |
Correct |
2813 ms |
9960 KB |
Output is correct |
8 |
Correct |
2753 ms |
9536 KB |
Output is correct |
9 |
Correct |
42 ms |
5880 KB |
Output is correct |
10 |
Correct |
1992 ms |
9476 KB |
Output is correct |
11 |
Correct |
1901 ms |
9348 KB |
Output is correct |
12 |
Correct |
1874 ms |
9568 KB |
Output is correct |
13 |
Correct |
1890 ms |
9756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1989 ms |
7000 KB |
Output is correct |
2 |
Correct |
1221 ms |
5240 KB |
Output is correct |
3 |
Correct |
2125 ms |
6816 KB |
Output is correct |
4 |
Correct |
1944 ms |
7012 KB |
Output is correct |
5 |
Correct |
43 ms |
4472 KB |
Output is correct |
6 |
Correct |
2047 ms |
6852 KB |
Output is correct |
7 |
Correct |
1869 ms |
6812 KB |
Output is correct |
8 |
Correct |
1727 ms |
6908 KB |
Output is correct |
9 |
Correct |
1299 ms |
6492 KB |
Output is correct |
10 |
Correct |
1206 ms |
6112 KB |
Output is correct |
11 |
Correct |
1285 ms |
6780 KB |
Output is correct |
12 |
Correct |
1211 ms |
6688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2180 ms |
7652 KB |
Output is correct |
2 |
Correct |
42 ms |
6008 KB |
Output is correct |
3 |
Correct |
203 ms |
6516 KB |
Output is correct |
4 |
Correct |
124 ms |
6644 KB |
Output is correct |
5 |
Correct |
1592 ms |
9620 KB |
Output is correct |
6 |
Correct |
2206 ms |
10936 KB |
Output is correct |
7 |
Correct |
1585 ms |
9468 KB |
Output is correct |
8 |
Correct |
1103 ms |
8944 KB |
Output is correct |
9 |
Correct |
1098 ms |
9136 KB |
Output is correct |
10 |
Correct |
1083 ms |
8948 KB |
Output is correct |
11 |
Correct |
1776 ms |
9816 KB |
Output is correct |
12 |
Correct |
1715 ms |
9960 KB |
Output is correct |
13 |
Correct |
1734 ms |
9836 KB |
Output is correct |
14 |
Correct |
1436 ms |
9624 KB |
Output is correct |
15 |
Correct |
1500 ms |
9448 KB |
Output is correct |
16 |
Correct |
2337 ms |
10916 KB |
Output is correct |
17 |
Correct |
2247 ms |
10860 KB |
Output is correct |
18 |
Correct |
2280 ms |
11008 KB |
Output is correct |
19 |
Correct |
2265 ms |
10940 KB |
Output is correct |
20 |
Correct |
1987 ms |
10184 KB |
Output is correct |
21 |
Correct |
2007 ms |
10184 KB |
Output is correct |
22 |
Correct |
2179 ms |
11252 KB |
Output is correct |
23 |
Correct |
1641 ms |
9332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2515 ms |
8068 KB |
Output is correct |
2 |
Correct |
2452 ms |
10900 KB |
Output is correct |
3 |
Correct |
2439 ms |
10732 KB |
Output is correct |
4 |
Correct |
2460 ms |
10796 KB |
Output is correct |
5 |
Correct |
2405 ms |
11016 KB |
Output is correct |
6 |
Correct |
2847 ms |
9640 KB |
Output is correct |
7 |
Correct |
2813 ms |
9960 KB |
Output is correct |
8 |
Correct |
2753 ms |
9536 KB |
Output is correct |
9 |
Correct |
42 ms |
5880 KB |
Output is correct |
10 |
Correct |
1992 ms |
9476 KB |
Output is correct |
11 |
Correct |
1901 ms |
9348 KB |
Output is correct |
12 |
Correct |
1874 ms |
9568 KB |
Output is correct |
13 |
Correct |
1890 ms |
9756 KB |
Output is correct |
14 |
Correct |
1989 ms |
7000 KB |
Output is correct |
15 |
Correct |
1221 ms |
5240 KB |
Output is correct |
16 |
Correct |
2125 ms |
6816 KB |
Output is correct |
17 |
Correct |
1944 ms |
7012 KB |
Output is correct |
18 |
Correct |
43 ms |
4472 KB |
Output is correct |
19 |
Correct |
2047 ms |
6852 KB |
Output is correct |
20 |
Correct |
1869 ms |
6812 KB |
Output is correct |
21 |
Correct |
1727 ms |
6908 KB |
Output is correct |
22 |
Correct |
1299 ms |
6492 KB |
Output is correct |
23 |
Correct |
1206 ms |
6112 KB |
Output is correct |
24 |
Correct |
1285 ms |
6780 KB |
Output is correct |
25 |
Correct |
1211 ms |
6688 KB |
Output is correct |
26 |
Correct |
2709 ms |
10868 KB |
Output is correct |
27 |
Correct |
2922 ms |
10184 KB |
Output is correct |
28 |
Correct |
2634 ms |
10604 KB |
Output is correct |
29 |
Correct |
2305 ms |
10484 KB |
Output is correct |
30 |
Correct |
2916 ms |
10492 KB |
Output is correct |
31 |
Correct |
2901 ms |
10592 KB |
Output is correct |
32 |
Correct |
2934 ms |
10608 KB |
Output is correct |
33 |
Correct |
2752 ms |
10892 KB |
Output is correct |
34 |
Correct |
2720 ms |
10708 KB |
Output is correct |
35 |
Correct |
2710 ms |
11296 KB |
Output is correct |
36 |
Correct |
2397 ms |
10576 KB |
Output is correct |
37 |
Correct |
2377 ms |
10372 KB |
Output is correct |
38 |
Correct |
2334 ms |
10660 KB |
Output is correct |
39 |
Correct |
1863 ms |
9832 KB |
Output is correct |
40 |
Correct |
1906 ms |
10172 KB |
Output is correct |
41 |
Correct |
1901 ms |
10156 KB |
Output is correct |
42 |
Correct |
1821 ms |
10528 KB |
Output is correct |
43 |
Correct |
1780 ms |
10708 KB |
Output is correct |
44 |
Correct |
1808 ms |
10772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
Output is correct |
2 |
Correct |
2 ms |
2688 KB |
Output is correct |
3 |
Correct |
70 ms |
2936 KB |
Output is correct |
4 |
Correct |
6 ms |
2944 KB |
Output is correct |
5 |
Correct |
44 ms |
3064 KB |
Output is correct |
6 |
Correct |
42 ms |
2936 KB |
Output is correct |
7 |
Correct |
42 ms |
2936 KB |
Output is correct |
8 |
Correct |
39 ms |
2936 KB |
Output is correct |
9 |
Correct |
48 ms |
2936 KB |
Output is correct |
10 |
Correct |
39 ms |
2936 KB |
Output is correct |
11 |
Correct |
38 ms |
2936 KB |
Output is correct |
12 |
Correct |
40 ms |
2936 KB |
Output is correct |
13 |
Correct |
48 ms |
2936 KB |
Output is correct |
14 |
Correct |
46 ms |
2936 KB |
Output is correct |
15 |
Correct |
47 ms |
2928 KB |
Output is correct |
16 |
Correct |
43 ms |
2936 KB |
Output is correct |
17 |
Correct |
42 ms |
2936 KB |
Output is correct |
18 |
Correct |
2515 ms |
8068 KB |
Output is correct |
19 |
Correct |
2452 ms |
10900 KB |
Output is correct |
20 |
Correct |
2439 ms |
10732 KB |
Output is correct |
21 |
Correct |
2460 ms |
10796 KB |
Output is correct |
22 |
Correct |
2405 ms |
11016 KB |
Output is correct |
23 |
Correct |
2847 ms |
9640 KB |
Output is correct |
24 |
Correct |
2813 ms |
9960 KB |
Output is correct |
25 |
Correct |
2753 ms |
9536 KB |
Output is correct |
26 |
Correct |
42 ms |
5880 KB |
Output is correct |
27 |
Correct |
1992 ms |
9476 KB |
Output is correct |
28 |
Correct |
1901 ms |
9348 KB |
Output is correct |
29 |
Correct |
1874 ms |
9568 KB |
Output is correct |
30 |
Correct |
1890 ms |
9756 KB |
Output is correct |
31 |
Correct |
1989 ms |
7000 KB |
Output is correct |
32 |
Correct |
1221 ms |
5240 KB |
Output is correct |
33 |
Correct |
2125 ms |
6816 KB |
Output is correct |
34 |
Correct |
1944 ms |
7012 KB |
Output is correct |
35 |
Correct |
43 ms |
4472 KB |
Output is correct |
36 |
Correct |
2047 ms |
6852 KB |
Output is correct |
37 |
Correct |
1869 ms |
6812 KB |
Output is correct |
38 |
Correct |
1727 ms |
6908 KB |
Output is correct |
39 |
Correct |
1299 ms |
6492 KB |
Output is correct |
40 |
Correct |
1206 ms |
6112 KB |
Output is correct |
41 |
Correct |
1285 ms |
6780 KB |
Output is correct |
42 |
Correct |
1211 ms |
6688 KB |
Output is correct |
43 |
Correct |
2180 ms |
7652 KB |
Output is correct |
44 |
Correct |
42 ms |
6008 KB |
Output is correct |
45 |
Correct |
203 ms |
6516 KB |
Output is correct |
46 |
Correct |
124 ms |
6644 KB |
Output is correct |
47 |
Correct |
1592 ms |
9620 KB |
Output is correct |
48 |
Correct |
2206 ms |
10936 KB |
Output is correct |
49 |
Correct |
1585 ms |
9468 KB |
Output is correct |
50 |
Correct |
1103 ms |
8944 KB |
Output is correct |
51 |
Correct |
1098 ms |
9136 KB |
Output is correct |
52 |
Correct |
1083 ms |
8948 KB |
Output is correct |
53 |
Correct |
1776 ms |
9816 KB |
Output is correct |
54 |
Correct |
1715 ms |
9960 KB |
Output is correct |
55 |
Correct |
1734 ms |
9836 KB |
Output is correct |
56 |
Correct |
1436 ms |
9624 KB |
Output is correct |
57 |
Correct |
1500 ms |
9448 KB |
Output is correct |
58 |
Correct |
2337 ms |
10916 KB |
Output is correct |
59 |
Correct |
2247 ms |
10860 KB |
Output is correct |
60 |
Correct |
2280 ms |
11008 KB |
Output is correct |
61 |
Correct |
2265 ms |
10940 KB |
Output is correct |
62 |
Correct |
1987 ms |
10184 KB |
Output is correct |
63 |
Correct |
2007 ms |
10184 KB |
Output is correct |
64 |
Correct |
2179 ms |
11252 KB |
Output is correct |
65 |
Correct |
1641 ms |
9332 KB |
Output is correct |
66 |
Correct |
2709 ms |
10868 KB |
Output is correct |
67 |
Correct |
2922 ms |
10184 KB |
Output is correct |
68 |
Correct |
2634 ms |
10604 KB |
Output is correct |
69 |
Correct |
2305 ms |
10484 KB |
Output is correct |
70 |
Correct |
2916 ms |
10492 KB |
Output is correct |
71 |
Correct |
2901 ms |
10592 KB |
Output is correct |
72 |
Correct |
2934 ms |
10608 KB |
Output is correct |
73 |
Correct |
2752 ms |
10892 KB |
Output is correct |
74 |
Correct |
2720 ms |
10708 KB |
Output is correct |
75 |
Correct |
2710 ms |
11296 KB |
Output is correct |
76 |
Correct |
2397 ms |
10576 KB |
Output is correct |
77 |
Correct |
2377 ms |
10372 KB |
Output is correct |
78 |
Correct |
2334 ms |
10660 KB |
Output is correct |
79 |
Correct |
1863 ms |
9832 KB |
Output is correct |
80 |
Correct |
1906 ms |
10172 KB |
Output is correct |
81 |
Correct |
1901 ms |
10156 KB |
Output is correct |
82 |
Correct |
1821 ms |
10528 KB |
Output is correct |
83 |
Correct |
1780 ms |
10708 KB |
Output is correct |
84 |
Correct |
1808 ms |
10772 KB |
Output is correct |
85 |
Execution timed out |
3077 ms |
11068 KB |
Time limit exceeded |
86 |
Halted |
0 ms |
0 KB |
- |