# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
383088 |
2021-03-28T19:45:34 Z |
Tekor |
Bridges (APIO19_bridges) |
C++17 |
|
2577 ms |
6060 KB |
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define ld long double
#define pii pair <int,int>
#define pll pair <ll,ll>
#define pil pair <int,ll>
#define pli pair <ll,int>
#define pss pair <short,short>
#define ull unsigned long long
#define pdd pair <ld,ld>
#define pb push_back
#define mp make_pair
#define puu pair<ull,ull>
#define pvv pair<vector<int>, vector<int> >
#define _bp __builtin_popcount
#define ptt pair <pnode,pnode>
#define all(v) v.begin(),v.end()
#define en "\n"
void file()
{
freopen("input.txt","r",stdin);
freopen("f.txt","w",stdout);
}
void boos()
{
ios_base :: sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
//const long double pi = acos(-1);
const ll INF = (ll)1e9 + 7ll;
const ll INF1 = 998244353;
const ll INF2 = (ll)1e9 + 9ll;
const ll LLINF = (ll)1e18;
const ll INTmx = (ll)1e9;
const ld EPS = (ld)1e-15;
const int N = 1e5 + 100;
const int bl = 830;
int dsu[N],sz[N],last[N],ans[N],val[N],n,m;
bool ban[N],tt[N];
pair <pii,pii> reb[N];
pair <pii,pii> reb1[N];
vector <pair<pii,pii> > dob;
vector <pair <int,pii> > zap;
bool cmp(pair <pii,pii> x,pair <pii,pii> y)
{
return x.f.f > y.f.f;
}
bool cmp1(pair <int,pii> x,pair <int,pii> y)
{
return x.f > y.f;
}
int getroot(int v)
{
return dsu[v] == v ? v : dsu[v] = getroot(dsu[v]);
}
int getroot1(int v)
{
return dsu[v] == v ? v : getroot1(dsu[v]);
}
void merg(int v,int u)
{
v = getroot(v);
u = getroot(u);
if(v == u)return;
if(sz[v] >= sz[u])
{
dsu[u] = v;
sz[v] += sz[u];
}else {
dsu[v] = u;
sz[u] += sz[v];
}
}
vector <pair <int,pii> > calb;
void merg1(int v,int u)
{
v = getroot1(v);
u = getroot1(u);
if(v == u)return;
calb.pb(mp(u,mp(u,sz[u])));
calb.pb(mp(v,mp(v,sz[v])));
if(sz[v] >= sz[u])
{
dsu[u] = v;
sz[v] += sz[u];
}else {
dsu[v] = u;
sz[u] += sz[v];
}
}
void fin(int s,int w,int num)
{
for(int i = 0;i < dob.size();i++)
{
if(w <= dob[i].s.s && dob[i].f.f <= num && dob[i].f.s >= num)
{
merg1(reb1[dob[i].s.f].s.f,reb1[dob[i].s.f].s.s);
}
}
ans[num] = sz[getroot1(s)];
while(!calb.empty())
{
dsu[calb.back().f] = calb.back().s.f;
sz[calb.back().f] = calb.back().s.s;
calb.pop_back();
}
}
int main()
{
boos();
//file();
cin >> n >> m;
for(int i = 1;i <= m;i++)
{
cin >> reb[i].s.f >> reb[i].s.s >> reb[i].f.f;
reb[i].f.s = i;
reb1[i] = reb[i];
last[i] = 1;
val[i] = reb[i].f.f;
}
sort(reb + 1,reb + m + 1,cmp);
int q;
cin >> q;
for(int t = 1;t <= q;t++)
{
int typ;
cin >> typ;
if(typ == 1)
{
int num,x;
cin >> num >> x;
ban[num] = 1;
if(last[num] < t)dob.pb(mp(mp(last[num],t - 1),mp(num,val[num])));
last[num] = t;
val[num] = x;
}else {
int s,w;
cin >> s >> w;
tt[t] = 1;
zap.pb(mp(w,mp(s,t)));
}
if(t % bl && t != q)continue;
sort(all(zap),cmp1);
int R = 0;
for(int i = 1;i <= m;i++)
{
if(ban[i])
{
dob.pb(mp(mp(last[i],t),mp(i,val[i])));
}
}
for(int i = 1;i <= n;i++)
{
dsu[i] = i;
sz[i] = 1;
}
for(int i = 1;i <= m;i++)
{
while(R < zap.size() && zap[R].f > reb[i].f.f)
{
fin(zap[R].s.f,zap[R].f,zap[R].s.s);
R++;
}
if(ban[reb[i].f.s])continue;
merg(reb[i].s.f,reb[i].s.s);
}
while(R < zap.size())
{
fin(zap[R].s.f,zap[R].f,zap[R].s.s);
R++;
}
zap.clear();
for(int i = 0;i < dob.size();i++)
{
reb1[dob[i].s.f].f.f = dob[i].s.s;
}
dob.clear();
for(int i = 1;i <= m;i++)
{
ban[i] = 0;
last[i] = t + 1;
reb[i] = reb1[i];
}
sort(reb + 1,reb + m + 1,cmp);
}
for(int i = 1;i <= q;i++)
{
if(tt[i])
{
cout << ans[i] << en;
}
}
}
Compilation message
bridges.cpp: In function 'void fin(int, int, int)':
bridges.cpp:97:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int i = 0;i < dob.size();i++)
| ~~^~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:163:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | while(R < zap.size() && zap[R].f > reb[i].f.f)
| ~~^~~~~~~~~~~~
bridges.cpp:171:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
171 | while(R < zap.size())
| ~~^~~~~~~~~~~~
bridges.cpp:177:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
177 | for(int i = 0;i < dob.size();i++)
| ~~^~~~~~~~~~~~
bridges.cpp: In function 'void file()':
bridges.cpp:24:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
24 | freopen("input.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
25 | freopen("f.txt","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
35 ms |
492 KB |
Output is correct |
4 |
Correct |
5 ms |
492 KB |
Output is correct |
5 |
Correct |
21 ms |
492 KB |
Output is correct |
6 |
Correct |
22 ms |
492 KB |
Output is correct |
7 |
Correct |
23 ms |
492 KB |
Output is correct |
8 |
Correct |
23 ms |
492 KB |
Output is correct |
9 |
Correct |
28 ms |
492 KB |
Output is correct |
10 |
Correct |
25 ms |
492 KB |
Output is correct |
11 |
Correct |
26 ms |
492 KB |
Output is correct |
12 |
Correct |
28 ms |
492 KB |
Output is correct |
13 |
Correct |
32 ms |
492 KB |
Output is correct |
14 |
Correct |
30 ms |
492 KB |
Output is correct |
15 |
Correct |
27 ms |
492 KB |
Output is correct |
16 |
Correct |
26 ms |
492 KB |
Output is correct |
17 |
Correct |
25 ms |
496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1700 ms |
3588 KB |
Output is correct |
2 |
Correct |
1728 ms |
3564 KB |
Output is correct |
3 |
Correct |
1745 ms |
3568 KB |
Output is correct |
4 |
Correct |
1753 ms |
3728 KB |
Output is correct |
5 |
Correct |
1742 ms |
3716 KB |
Output is correct |
6 |
Correct |
2467 ms |
3944 KB |
Output is correct |
7 |
Correct |
2504 ms |
3952 KB |
Output is correct |
8 |
Correct |
2470 ms |
3944 KB |
Output is correct |
9 |
Correct |
43 ms |
1132 KB |
Output is correct |
10 |
Correct |
1578 ms |
3592 KB |
Output is correct |
11 |
Correct |
1501 ms |
3588 KB |
Output is correct |
12 |
Correct |
1547 ms |
4012 KB |
Output is correct |
13 |
Correct |
1529 ms |
3820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1317 ms |
2736 KB |
Output is correct |
2 |
Correct |
979 ms |
1548 KB |
Output is correct |
3 |
Correct |
1513 ms |
2796 KB |
Output is correct |
4 |
Correct |
1308 ms |
2732 KB |
Output is correct |
5 |
Correct |
43 ms |
1132 KB |
Output is correct |
6 |
Correct |
1439 ms |
2832 KB |
Output is correct |
7 |
Correct |
1193 ms |
2668 KB |
Output is correct |
8 |
Correct |
1069 ms |
2568 KB |
Output is correct |
9 |
Correct |
886 ms |
3072 KB |
Output is correct |
10 |
Correct |
810 ms |
2828 KB |
Output is correct |
11 |
Correct |
917 ms |
2796 KB |
Output is correct |
12 |
Correct |
834 ms |
2792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2032 ms |
5892 KB |
Output is correct |
2 |
Correct |
43 ms |
1132 KB |
Output is correct |
3 |
Correct |
231 ms |
4440 KB |
Output is correct |
4 |
Correct |
150 ms |
4460 KB |
Output is correct |
5 |
Correct |
1354 ms |
5788 KB |
Output is correct |
6 |
Correct |
2051 ms |
5796 KB |
Output is correct |
7 |
Correct |
1343 ms |
6060 KB |
Output is correct |
8 |
Correct |
1016 ms |
3712 KB |
Output is correct |
9 |
Correct |
997 ms |
3712 KB |
Output is correct |
10 |
Correct |
996 ms |
3848 KB |
Output is correct |
11 |
Correct |
1582 ms |
4720 KB |
Output is correct |
12 |
Correct |
1561 ms |
4716 KB |
Output is correct |
13 |
Correct |
1568 ms |
5016 KB |
Output is correct |
14 |
Correct |
1273 ms |
5996 KB |
Output is correct |
15 |
Correct |
1366 ms |
5884 KB |
Output is correct |
16 |
Correct |
2032 ms |
6004 KB |
Output is correct |
17 |
Correct |
2068 ms |
6020 KB |
Output is correct |
18 |
Correct |
2065 ms |
5676 KB |
Output is correct |
19 |
Correct |
2050 ms |
5752 KB |
Output is correct |
20 |
Correct |
1748 ms |
5356 KB |
Output is correct |
21 |
Correct |
1763 ms |
5452 KB |
Output is correct |
22 |
Correct |
1967 ms |
5740 KB |
Output is correct |
23 |
Correct |
1281 ms |
5308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1700 ms |
3588 KB |
Output is correct |
2 |
Correct |
1728 ms |
3564 KB |
Output is correct |
3 |
Correct |
1745 ms |
3568 KB |
Output is correct |
4 |
Correct |
1753 ms |
3728 KB |
Output is correct |
5 |
Correct |
1742 ms |
3716 KB |
Output is correct |
6 |
Correct |
2467 ms |
3944 KB |
Output is correct |
7 |
Correct |
2504 ms |
3952 KB |
Output is correct |
8 |
Correct |
2470 ms |
3944 KB |
Output is correct |
9 |
Correct |
43 ms |
1132 KB |
Output is correct |
10 |
Correct |
1578 ms |
3592 KB |
Output is correct |
11 |
Correct |
1501 ms |
3588 KB |
Output is correct |
12 |
Correct |
1547 ms |
4012 KB |
Output is correct |
13 |
Correct |
1529 ms |
3820 KB |
Output is correct |
14 |
Correct |
1317 ms |
2736 KB |
Output is correct |
15 |
Correct |
979 ms |
1548 KB |
Output is correct |
16 |
Correct |
1513 ms |
2796 KB |
Output is correct |
17 |
Correct |
1308 ms |
2732 KB |
Output is correct |
18 |
Correct |
43 ms |
1132 KB |
Output is correct |
19 |
Correct |
1439 ms |
2832 KB |
Output is correct |
20 |
Correct |
1193 ms |
2668 KB |
Output is correct |
21 |
Correct |
1069 ms |
2568 KB |
Output is correct |
22 |
Correct |
886 ms |
3072 KB |
Output is correct |
23 |
Correct |
810 ms |
2828 KB |
Output is correct |
24 |
Correct |
917 ms |
2796 KB |
Output is correct |
25 |
Correct |
834 ms |
2792 KB |
Output is correct |
26 |
Correct |
1663 ms |
3440 KB |
Output is correct |
27 |
Correct |
2013 ms |
3744 KB |
Output is correct |
28 |
Correct |
1749 ms |
3460 KB |
Output is correct |
29 |
Correct |
1310 ms |
3692 KB |
Output is correct |
30 |
Correct |
2005 ms |
3832 KB |
Output is correct |
31 |
Correct |
2024 ms |
3872 KB |
Output is correct |
32 |
Correct |
2017 ms |
3948 KB |
Output is correct |
33 |
Correct |
1745 ms |
3692 KB |
Output is correct |
34 |
Correct |
1756 ms |
3640 KB |
Output is correct |
35 |
Correct |
1749 ms |
3588 KB |
Output is correct |
36 |
Correct |
1383 ms |
3668 KB |
Output is correct |
37 |
Correct |
1357 ms |
3576 KB |
Output is correct |
38 |
Correct |
1352 ms |
3820 KB |
Output is correct |
39 |
Correct |
1137 ms |
3564 KB |
Output is correct |
40 |
Correct |
1109 ms |
3564 KB |
Output is correct |
41 |
Correct |
1114 ms |
3564 KB |
Output is correct |
42 |
Correct |
1139 ms |
3580 KB |
Output is correct |
43 |
Correct |
1129 ms |
3564 KB |
Output is correct |
44 |
Correct |
1132 ms |
3324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
35 ms |
492 KB |
Output is correct |
4 |
Correct |
5 ms |
492 KB |
Output is correct |
5 |
Correct |
21 ms |
492 KB |
Output is correct |
6 |
Correct |
22 ms |
492 KB |
Output is correct |
7 |
Correct |
23 ms |
492 KB |
Output is correct |
8 |
Correct |
23 ms |
492 KB |
Output is correct |
9 |
Correct |
28 ms |
492 KB |
Output is correct |
10 |
Correct |
25 ms |
492 KB |
Output is correct |
11 |
Correct |
26 ms |
492 KB |
Output is correct |
12 |
Correct |
28 ms |
492 KB |
Output is correct |
13 |
Correct |
32 ms |
492 KB |
Output is correct |
14 |
Correct |
30 ms |
492 KB |
Output is correct |
15 |
Correct |
27 ms |
492 KB |
Output is correct |
16 |
Correct |
26 ms |
492 KB |
Output is correct |
17 |
Correct |
25 ms |
496 KB |
Output is correct |
18 |
Correct |
1700 ms |
3588 KB |
Output is correct |
19 |
Correct |
1728 ms |
3564 KB |
Output is correct |
20 |
Correct |
1745 ms |
3568 KB |
Output is correct |
21 |
Correct |
1753 ms |
3728 KB |
Output is correct |
22 |
Correct |
1742 ms |
3716 KB |
Output is correct |
23 |
Correct |
2467 ms |
3944 KB |
Output is correct |
24 |
Correct |
2504 ms |
3952 KB |
Output is correct |
25 |
Correct |
2470 ms |
3944 KB |
Output is correct |
26 |
Correct |
43 ms |
1132 KB |
Output is correct |
27 |
Correct |
1578 ms |
3592 KB |
Output is correct |
28 |
Correct |
1501 ms |
3588 KB |
Output is correct |
29 |
Correct |
1547 ms |
4012 KB |
Output is correct |
30 |
Correct |
1529 ms |
3820 KB |
Output is correct |
31 |
Correct |
1317 ms |
2736 KB |
Output is correct |
32 |
Correct |
979 ms |
1548 KB |
Output is correct |
33 |
Correct |
1513 ms |
2796 KB |
Output is correct |
34 |
Correct |
1308 ms |
2732 KB |
Output is correct |
35 |
Correct |
43 ms |
1132 KB |
Output is correct |
36 |
Correct |
1439 ms |
2832 KB |
Output is correct |
37 |
Correct |
1193 ms |
2668 KB |
Output is correct |
38 |
Correct |
1069 ms |
2568 KB |
Output is correct |
39 |
Correct |
886 ms |
3072 KB |
Output is correct |
40 |
Correct |
810 ms |
2828 KB |
Output is correct |
41 |
Correct |
917 ms |
2796 KB |
Output is correct |
42 |
Correct |
834 ms |
2792 KB |
Output is correct |
43 |
Correct |
2032 ms |
5892 KB |
Output is correct |
44 |
Correct |
43 ms |
1132 KB |
Output is correct |
45 |
Correct |
231 ms |
4440 KB |
Output is correct |
46 |
Correct |
150 ms |
4460 KB |
Output is correct |
47 |
Correct |
1354 ms |
5788 KB |
Output is correct |
48 |
Correct |
2051 ms |
5796 KB |
Output is correct |
49 |
Correct |
1343 ms |
6060 KB |
Output is correct |
50 |
Correct |
1016 ms |
3712 KB |
Output is correct |
51 |
Correct |
997 ms |
3712 KB |
Output is correct |
52 |
Correct |
996 ms |
3848 KB |
Output is correct |
53 |
Correct |
1582 ms |
4720 KB |
Output is correct |
54 |
Correct |
1561 ms |
4716 KB |
Output is correct |
55 |
Correct |
1568 ms |
5016 KB |
Output is correct |
56 |
Correct |
1273 ms |
5996 KB |
Output is correct |
57 |
Correct |
1366 ms |
5884 KB |
Output is correct |
58 |
Correct |
2032 ms |
6004 KB |
Output is correct |
59 |
Correct |
2068 ms |
6020 KB |
Output is correct |
60 |
Correct |
2065 ms |
5676 KB |
Output is correct |
61 |
Correct |
2050 ms |
5752 KB |
Output is correct |
62 |
Correct |
1748 ms |
5356 KB |
Output is correct |
63 |
Correct |
1763 ms |
5452 KB |
Output is correct |
64 |
Correct |
1967 ms |
5740 KB |
Output is correct |
65 |
Correct |
1281 ms |
5308 KB |
Output is correct |
66 |
Correct |
1663 ms |
3440 KB |
Output is correct |
67 |
Correct |
2013 ms |
3744 KB |
Output is correct |
68 |
Correct |
1749 ms |
3460 KB |
Output is correct |
69 |
Correct |
1310 ms |
3692 KB |
Output is correct |
70 |
Correct |
2005 ms |
3832 KB |
Output is correct |
71 |
Correct |
2024 ms |
3872 KB |
Output is correct |
72 |
Correct |
2017 ms |
3948 KB |
Output is correct |
73 |
Correct |
1745 ms |
3692 KB |
Output is correct |
74 |
Correct |
1756 ms |
3640 KB |
Output is correct |
75 |
Correct |
1749 ms |
3588 KB |
Output is correct |
76 |
Correct |
1383 ms |
3668 KB |
Output is correct |
77 |
Correct |
1357 ms |
3576 KB |
Output is correct |
78 |
Correct |
1352 ms |
3820 KB |
Output is correct |
79 |
Correct |
1137 ms |
3564 KB |
Output is correct |
80 |
Correct |
1109 ms |
3564 KB |
Output is correct |
81 |
Correct |
1114 ms |
3564 KB |
Output is correct |
82 |
Correct |
1139 ms |
3580 KB |
Output is correct |
83 |
Correct |
1129 ms |
3564 KB |
Output is correct |
84 |
Correct |
1132 ms |
3324 KB |
Output is correct |
85 |
Correct |
2476 ms |
5680 KB |
Output is correct |
86 |
Correct |
257 ms |
4588 KB |
Output is correct |
87 |
Correct |
177 ms |
4460 KB |
Output is correct |
88 |
Correct |
1775 ms |
5612 KB |
Output is correct |
89 |
Correct |
2454 ms |
5728 KB |
Output is correct |
90 |
Correct |
1790 ms |
5620 KB |
Output is correct |
91 |
Correct |
1795 ms |
3592 KB |
Output is correct |
92 |
Correct |
1793 ms |
3536 KB |
Output is correct |
93 |
Correct |
2519 ms |
3876 KB |
Output is correct |
94 |
Correct |
2134 ms |
4460 KB |
Output is correct |
95 |
Correct |
2142 ms |
4460 KB |
Output is correct |
96 |
Correct |
2235 ms |
4588 KB |
Output is correct |
97 |
Correct |
1496 ms |
5868 KB |
Output is correct |
98 |
Correct |
1539 ms |
5424 KB |
Output is correct |
99 |
Correct |
2525 ms |
5764 KB |
Output is correct |
100 |
Correct |
2505 ms |
5456 KB |
Output is correct |
101 |
Correct |
2577 ms |
5640 KB |
Output is correct |
102 |
Correct |
2560 ms |
5492 KB |
Output is correct |
103 |
Correct |
2372 ms |
5224 KB |
Output is correct |
104 |
Correct |
2360 ms |
5228 KB |
Output is correct |
105 |
Correct |
2000 ms |
4844 KB |
Output is correct |
106 |
Correct |
1689 ms |
4332 KB |
Output is correct |
107 |
Correct |
1947 ms |
5304 KB |
Output is correct |
108 |
Correct |
2438 ms |
5500 KB |
Output is correct |
109 |
Correct |
1768 ms |
4844 KB |
Output is correct |