#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
// Miscellanous
#define gc getchar_unlocked
#define ll long long
#define ull unsigned long long
#define si(x) scanf("%d",&x)
#define si2(x,y) scanf("%d %d",&x,&y)
#define sl(x) scanf("%lld",&x)
#define sl2(x,y) scanf("%lld %lld",&x,&y)
#define sstr(s) cin >> s
#define pi(x) printf("%d\n",x)
#define pi2(x,y) printf("%d %d\n",x,y)
#define pl(x) printf("%lld\n",x)
#define pl2(x,y) printf("%lld %lld\n",x,y)
#define ps(s) cout << s << endl
#define py printf("YES\n")
#define pn printf("NO\n")
#define pnl printf("\n")
#define pb push_back
#define ff first
#define ss second
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define sortv(v) sort(all(v))
#define revsort(v) sort(v.rbegin(),v.rend())
#define reverse(v) reverse(all(v))
#define alla(arr,sz) arr,arr+sz
#define sorta(arr,sz) sort(alla(arr,sz))
#define reversea(arr,sz) reverse(alla(arr,sz))
#define cta(x,v) count(alla(arr,sz),x)
#define ct(x,v) count(all(v),x)
#define cto(v) count_if(all(v),[] (int a) {return a%2 == 1;})
#define cte(v) count_if(all(v),[] (int a) {return a%2 == 0;})
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define clr(x) memset(x, 0, sizeof(x))
// Loops
#define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
#define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
#define forc(c,s,e) for (char (c)=(s);(c)<=(e);++(c))
#define forr(i,s,e) for (int (i)=(s);(i)>=(e);--(i))
#define foreach(val,cont) for (auto &(val) : (cont))
#define rep(i,n) loop(i,0,n)
#define repn(i,n) loope(i,1,n)
// Constants
#define PI 3.1415926535897932384626
#define sqr(x) ((x) * 1ll * (x))
const int mod = 1000000007;
// Containers
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<string,string> pss;
typedef map<int, int> mii;
// Input Output
struct edge
{
int u,v,wt;
bool operator<(const edge &x) const {return wt < x.wt;}
void read() {scanf("%d %d %d" , &u, &v, &wt);}
};
#define takei(a) int a; si(a)
#define takei2(a,b) int a,b; si2(a,b)
#define takel(a) ll a; sl(a)
#define takel2(a,b) ll a,b; sl2(a,b)
#define takearri0(n,a) vi a(n); rep(i,n) si(a[i])
#define takearri1(n,a) vi a(n+1); a[0] = 0; repn(i,n) si(a[i])
#define takearrl0(n,a) vl a(n); rep(i,n) sl(a[i])
#define takearrl1(n,a) vl a(n+1); a[0] = 0ll; repn(i,n) sl(a[i])
// Debug
void _print(int t) {cerr << t;}
void _print(ll t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
void _print(edge t) {cerr << "[ " << '{' << t.u << ',' << t.v << "} " << t.wt << " ]";}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(unordered_set <T> v);
template <class T> void _print(unordered_multiset <T> v);
template <class T> void _print(set <T> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(unordered_map <T, V> v);
template <class T, class V> void _print(unordered_multimap <T, V> v);
template <class T, class V> void _print(map <T, V> v);
template <class T, class V> void _print(multimap <T, V> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(unordered_set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(unordered_multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(unordered_map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(unordered_multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
#ifndef ONLINE_JUDGE
#define deb(x) cerr << #x << " = "; _print(x); cerr << endl;
#else
#define deb(x)
#endif
inline string inttostr(ll a){
char x[100];
sprintf(x,"%lld",a); string s = x;
return s;
}
inline ll strtoint(string a){
char x[100]; ll res;
strcpy(x,a.c_str()); sscanf(x,"%lld",&res);
return res;
}
inline string getstr(void){
char x[1000005];
scanf("%s",x); string s = x;
return s;
}
inline string uppercase(string s){
int n = sz(s);
rep(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
return s;
}
inline string lowercase(string s){
int n = sz(s);
rep(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
return s;
}
// ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
// Link --> https://oj.uz/problem/view/APIO19_bridges
// Explanation --> https://codeforces.com/blog/entry/67129#:~:text=Brief%20Outline%3A%20Divide,DSU%20with%20rollbacks.
// https://codeforces.com/blog/entry/67129#:~:text=You%20don%27t%20need,vertex%20with%20weight.)
// Divide the queries into sqrt(q) blocks.
// For each block, AT MOST sqrt(q) edges have weights changed within the block.
// Sort all the queries by decreasing weight in the block, and maintain a DSU while
// adding edges that are ** UNCHANGED ** within the block one-by-one in
// DECREASING order of WEIGHT
// And to answer each query, just simply connect the extra "CHANGED" edges
// on the COMPRESSED VERTICES and run DFS, i.e. just regard a connected component
// as a single vertex with weight
const int MAXN = 5e4;
vi adj[MAXN+1];
int color[MAXN+1];
int size_[MAXN+1] , parent[MAXN+1];
bool vis2[MAXN+1];
// DSU ----------------------------------------------------------
void reset(int n)
{
repn(i,n) size_[i] = 1;
repn(i,n) parent[i] = i;
}
int find_par(int node)
{
if(parent[node] == node) return node;
return parent[node] = find_par(parent[node]);
}
void size_union(int x, int y)
{
x = find_par(x);
y = find_par(y);
if(x == y) return;
if(size_[x] < size_[y]) {parent[x] = y; size_[y] += size_[x];}
else {parent[y] = x; size_[x] += size_[y];}
}
bool connected(int x, int y)
{
return find_par(x) == find_par(y);
}
// --------------------------------------------------------------
void add_edge(int u, int v)
{
adj[u].pb(v);
adj[v].pb(u);
}
void dfs(int u, int &ans)
{
if(vis2[u]) return;
vis2[u] = 1;
ans += size_[u];
for(auto v : adj[u]) dfs(v,ans);
}
int main()
{
const int B_SIZE = 500;
takei2(n,m);
vector<edge> edges(m+1);
repn(i,m) edges[i].read();
bool change[m+1];
bool chk[m+1];
vi to_add[B_SIZE];
int answer[B_SIZE];
takei(q);
for (int l = 0; l < q; l += B_SIZE)
{
int r = min(q - 1 , l + B_SIZE - 1);
vvi cur_q(r-l+1);
vi ask, upd;
clr(change);
rep(i,r-l+1)
{
takei(t);
takei2(id,wt);
cur_q[i] = {t,id,wt};
if(t == 1) change[id] = 1, upd.pb(i);
else ask.pb(i);
}
rep(i,r-l+1)
{
int &t = cur_q[i][0] , &id = cur_q[i][1] , &wt = cur_q[i][2];
if(t == 1) edges[id].wt = wt;
else
{
to_add[i].clear();
for(auto &j : upd) chk[cur_q[j][1]] = 0;
for(auto &j : upd)
{
int id2 = cur_q[j][1];
if(edges[id2].wt >= wt and !chk[id2]) to_add[i].pb(id2) , chk[id2] = 1;
}
}
}
vi unchanged;
repn(i,m) if(!change[i]) unchanged.pb(i);
sort(all(unchanged) , [&] (int i, int j) {return edges[i].wt > edges[j].wt;});
sort(all(ask) , [&] (int i, int j) {return cur_q[i][2] > cur_q[j][2];});
reset(n);
int j = 0, s = sz(unchanged);
for(auto &i : ask)
{
int start = cur_q[i][1];
int car_wt = cur_q[i][2];
while(j < s)
{
edge &ed = edges[unchanged[j]];
if(ed.wt >= car_wt) size_union(ed.u,ed.v) , j++;
else break;
}
// Adding GOOD edges from the CHANGING edges
vpii eds;
for(auto &id : to_add[i])
{
edge &ed = edges[id];
int u = find_par(ed.u);
int v = find_par(ed.v);
if(u != v) adj[u].clear(), adj[v].clear(), vis2[u] = vis2[v] = 0, eds.pb({u,v});
}
start = find_par(start);
adj[start].clear() , vis2[start] = 0;
for(auto &pr : eds) add_edge(pr.ff , pr.ss);
int ans = 0;
dfs(start , ans);
answer[i] = ans;
}
rep(i,r-l+1) if(cur_q[i][0] == 2) pi(answer[i]);
}
return 0;
}
// ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Compilation message
bridges.cpp: In function 'std::string uppercase(std::string)':
bridges.cpp:45:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
45 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
bridges.cpp:50:18: note: in expansion of macro 'loop'
50 | #define rep(i,n) loop(i,0,n)
| ^~~~
bridges.cpp:151:3: note: in expansion of macro 'rep'
151 | rep(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
| ^~~
bridges.cpp: In function 'std::string lowercase(std::string)':
bridges.cpp:45:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
45 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
bridges.cpp:50:18: note: in expansion of macro 'loop'
50 | #define rep(i,n) loop(i,0,n)
| ^~~~
bridges.cpp:157:3: note: in expansion of macro 'rep'
157 | rep(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
| ^~~
bridges.cpp: In function 'void reset(int)':
bridges.cpp:46:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
46 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
| ^
bridges.cpp:51:19: note: in expansion of macro 'loope'
51 | #define repn(i,n) loope(i,1,n)
| ^~~~~
bridges.cpp:188:5: note: in expansion of macro 'repn'
188 | repn(i,n) size_[i] = 1;
| ^~~~
bridges.cpp:46:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
46 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
| ^
bridges.cpp:51:19: note: in expansion of macro 'loope'
51 | #define repn(i,n) loope(i,1,n)
| ^~~~~
bridges.cpp:189:5: note: in expansion of macro 'repn'
189 | repn(i,n) parent[i] = i;
| ^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:46:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
46 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
| ^
bridges.cpp:51:19: note: in expansion of macro 'loope'
51 | #define repn(i,n) loope(i,1,n)
| ^~~~~
bridges.cpp:234:5: note: in expansion of macro 'repn'
234 | repn(i,m) edges[i].read();
| ^~~~
bridges.cpp:45:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
45 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
bridges.cpp:50:18: note: in expansion of macro 'loop'
50 | #define rep(i,n) loop(i,0,n)
| ^~~~
bridges.cpp:248:9: note: in expansion of macro 'rep'
248 | rep(i,r-l+1)
| ^~~
bridges.cpp:45:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
45 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
bridges.cpp:50:18: note: in expansion of macro 'loop'
50 | #define rep(i,n) loop(i,0,n)
| ^~~~
bridges.cpp:257:9: note: in expansion of macro 'rep'
257 | rep(i,r-l+1)
| ^~~
bridges.cpp:46:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
46 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
| ^
bridges.cpp:51:19: note: in expansion of macro 'loope'
51 | #define repn(i,n) loope(i,1,n)
| ^~~~~
bridges.cpp:276:9: note: in expansion of macro 'repn'
276 | repn(i,m) if(!change[i]) unchanged.pb(i);
| ^~~~
bridges.cpp:45:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
45 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
bridges.cpp:50:18: note: in expansion of macro 'loop'
50 | #define rep(i,n) loop(i,0,n)
| ^~~~
bridges.cpp:312:9: note: in expansion of macro 'rep'
312 | rep(i,r-l+1) if(cur_q[i][0] == 2) pi(answer[i]);
| ^~~
bridges.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define si2(x,y) scanf("%d %d",&x,&y)
| ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:81:30: note: in expansion of macro 'si2'
81 | #define takei2(a,b) int a,b; si2(a,b)
| ^~~
bridges.cpp:231:5: note: in expansion of macro 'takei2'
231 | takei2(n,m);
| ^~~~~~
bridges.cpp:11:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
11 | #define si(x) scanf("%d",&x)
| ~~~~~^~~~~~~~~
bridges.cpp:80:25: note: in expansion of macro 'si'
80 | #define takei(a) int a; si(a)
| ^~
bridges.cpp:241:5: note: in expansion of macro 'takei'
241 | takei(q);
| ^~~~~
bridges.cpp:11:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
11 | #define si(x) scanf("%d",&x)
| ~~~~~^~~~~~~~~
bridges.cpp:80:25: note: in expansion of macro 'si'
80 | #define takei(a) int a; si(a)
| ^~
bridges.cpp:250:13: note: in expansion of macro 'takei'
250 | takei(t);
| ^~~~~
bridges.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define si2(x,y) scanf("%d %d",&x,&y)
| ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:81:30: note: in expansion of macro 'si2'
81 | #define takei2(a,b) int a,b; si2(a,b)
| ^~~
bridges.cpp:251:13: note: in expansion of macro 'takei2'
251 | takei2(id,wt);
| ^~~~~~
bridges.cpp: In member function 'void edge::read()':
bridges.cpp:77:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | void read() {scanf("%d %d %d" , &u, &v, &wt);}
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1628 KB |
Output is correct |
2 |
Correct |
1 ms |
1628 KB |
Output is correct |
3 |
Correct |
16 ms |
2376 KB |
Output is correct |
4 |
Correct |
5 ms |
1628 KB |
Output is correct |
5 |
Correct |
18 ms |
2084 KB |
Output is correct |
6 |
Correct |
14 ms |
2068 KB |
Output is correct |
7 |
Correct |
16 ms |
1860 KB |
Output is correct |
8 |
Correct |
19 ms |
1884 KB |
Output is correct |
9 |
Correct |
17 ms |
2140 KB |
Output is correct |
10 |
Correct |
17 ms |
1884 KB |
Output is correct |
11 |
Correct |
18 ms |
1884 KB |
Output is correct |
12 |
Correct |
18 ms |
2080 KB |
Output is correct |
13 |
Correct |
21 ms |
1884 KB |
Output is correct |
14 |
Correct |
19 ms |
2112 KB |
Output is correct |
15 |
Correct |
19 ms |
1880 KB |
Output is correct |
16 |
Correct |
16 ms |
1896 KB |
Output is correct |
17 |
Correct |
17 ms |
1884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1335 ms |
8680 KB |
Output is correct |
2 |
Correct |
1335 ms |
8296 KB |
Output is correct |
3 |
Correct |
1346 ms |
8196 KB |
Output is correct |
4 |
Correct |
1319 ms |
8476 KB |
Output is correct |
5 |
Correct |
1353 ms |
8560 KB |
Output is correct |
6 |
Correct |
1526 ms |
7476 KB |
Output is correct |
7 |
Correct |
1443 ms |
7536 KB |
Output is correct |
8 |
Correct |
1442 ms |
7800 KB |
Output is correct |
9 |
Correct |
40 ms |
3164 KB |
Output is correct |
10 |
Correct |
773 ms |
7688 KB |
Output is correct |
11 |
Correct |
780 ms |
7364 KB |
Output is correct |
12 |
Correct |
1199 ms |
6500 KB |
Output is correct |
13 |
Correct |
1207 ms |
7572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
900 ms |
6996 KB |
Output is correct |
2 |
Correct |
439 ms |
4720 KB |
Output is correct |
3 |
Correct |
947 ms |
6896 KB |
Output is correct |
4 |
Correct |
930 ms |
6856 KB |
Output is correct |
5 |
Correct |
40 ms |
3156 KB |
Output is correct |
6 |
Correct |
911 ms |
7036 KB |
Output is correct |
7 |
Correct |
880 ms |
6684 KB |
Output is correct |
8 |
Correct |
846 ms |
6764 KB |
Output is correct |
9 |
Correct |
758 ms |
5716 KB |
Output is correct |
10 |
Correct |
742 ms |
5688 KB |
Output is correct |
11 |
Correct |
765 ms |
6984 KB |
Output is correct |
12 |
Correct |
741 ms |
7168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2365 ms |
8612 KB |
Output is correct |
2 |
Correct |
41 ms |
3152 KB |
Output is correct |
3 |
Correct |
225 ms |
5816 KB |
Output is correct |
4 |
Correct |
76 ms |
5940 KB |
Output is correct |
5 |
Correct |
1046 ms |
7152 KB |
Output is correct |
6 |
Correct |
2343 ms |
8868 KB |
Output is correct |
7 |
Correct |
1052 ms |
7352 KB |
Output is correct |
8 |
Correct |
1141 ms |
6120 KB |
Output is correct |
9 |
Correct |
1174 ms |
6340 KB |
Output is correct |
10 |
Correct |
1134 ms |
6104 KB |
Output is correct |
11 |
Correct |
1827 ms |
7708 KB |
Output is correct |
12 |
Correct |
1798 ms |
7540 KB |
Output is correct |
13 |
Correct |
1860 ms |
7516 KB |
Output is correct |
14 |
Correct |
904 ms |
7272 KB |
Output is correct |
15 |
Correct |
967 ms |
7260 KB |
Output is correct |
16 |
Correct |
2473 ms |
8668 KB |
Output is correct |
17 |
Correct |
2441 ms |
8584 KB |
Output is correct |
18 |
Correct |
2388 ms |
8736 KB |
Output is correct |
19 |
Correct |
2393 ms |
9324 KB |
Output is correct |
20 |
Correct |
2125 ms |
7896 KB |
Output is correct |
21 |
Correct |
2028 ms |
7736 KB |
Output is correct |
22 |
Correct |
2331 ms |
8580 KB |
Output is correct |
23 |
Correct |
1316 ms |
6628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1335 ms |
8680 KB |
Output is correct |
2 |
Correct |
1335 ms |
8296 KB |
Output is correct |
3 |
Correct |
1346 ms |
8196 KB |
Output is correct |
4 |
Correct |
1319 ms |
8476 KB |
Output is correct |
5 |
Correct |
1353 ms |
8560 KB |
Output is correct |
6 |
Correct |
1526 ms |
7476 KB |
Output is correct |
7 |
Correct |
1443 ms |
7536 KB |
Output is correct |
8 |
Correct |
1442 ms |
7800 KB |
Output is correct |
9 |
Correct |
40 ms |
3164 KB |
Output is correct |
10 |
Correct |
773 ms |
7688 KB |
Output is correct |
11 |
Correct |
780 ms |
7364 KB |
Output is correct |
12 |
Correct |
1199 ms |
6500 KB |
Output is correct |
13 |
Correct |
1207 ms |
7572 KB |
Output is correct |
14 |
Correct |
900 ms |
6996 KB |
Output is correct |
15 |
Correct |
439 ms |
4720 KB |
Output is correct |
16 |
Correct |
947 ms |
6896 KB |
Output is correct |
17 |
Correct |
930 ms |
6856 KB |
Output is correct |
18 |
Correct |
40 ms |
3156 KB |
Output is correct |
19 |
Correct |
911 ms |
7036 KB |
Output is correct |
20 |
Correct |
880 ms |
6684 KB |
Output is correct |
21 |
Correct |
846 ms |
6764 KB |
Output is correct |
22 |
Correct |
758 ms |
5716 KB |
Output is correct |
23 |
Correct |
742 ms |
5688 KB |
Output is correct |
24 |
Correct |
765 ms |
6984 KB |
Output is correct |
25 |
Correct |
741 ms |
7168 KB |
Output is correct |
26 |
Correct |
1363 ms |
8208 KB |
Output is correct |
27 |
Correct |
1470 ms |
8548 KB |
Output is correct |
28 |
Correct |
1383 ms |
8220 KB |
Output is correct |
29 |
Correct |
1287 ms |
7948 KB |
Output is correct |
30 |
Correct |
1500 ms |
8292 KB |
Output is correct |
31 |
Correct |
1547 ms |
8224 KB |
Output is correct |
32 |
Correct |
1569 ms |
8260 KB |
Output is correct |
33 |
Correct |
1406 ms |
8128 KB |
Output is correct |
34 |
Correct |
1454 ms |
8108 KB |
Output is correct |
35 |
Correct |
1403 ms |
8256 KB |
Output is correct |
36 |
Correct |
1292 ms |
7916 KB |
Output is correct |
37 |
Correct |
1288 ms |
7948 KB |
Output is correct |
38 |
Correct |
1303 ms |
8160 KB |
Output is correct |
39 |
Correct |
1214 ms |
6880 KB |
Output is correct |
40 |
Correct |
1202 ms |
6860 KB |
Output is correct |
41 |
Correct |
1251 ms |
6860 KB |
Output is correct |
42 |
Correct |
1178 ms |
8368 KB |
Output is correct |
43 |
Correct |
1184 ms |
8596 KB |
Output is correct |
44 |
Correct |
1177 ms |
8520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1628 KB |
Output is correct |
2 |
Correct |
1 ms |
1628 KB |
Output is correct |
3 |
Correct |
16 ms |
2376 KB |
Output is correct |
4 |
Correct |
5 ms |
1628 KB |
Output is correct |
5 |
Correct |
18 ms |
2084 KB |
Output is correct |
6 |
Correct |
14 ms |
2068 KB |
Output is correct |
7 |
Correct |
16 ms |
1860 KB |
Output is correct |
8 |
Correct |
19 ms |
1884 KB |
Output is correct |
9 |
Correct |
17 ms |
2140 KB |
Output is correct |
10 |
Correct |
17 ms |
1884 KB |
Output is correct |
11 |
Correct |
18 ms |
1884 KB |
Output is correct |
12 |
Correct |
18 ms |
2080 KB |
Output is correct |
13 |
Correct |
21 ms |
1884 KB |
Output is correct |
14 |
Correct |
19 ms |
2112 KB |
Output is correct |
15 |
Correct |
19 ms |
1880 KB |
Output is correct |
16 |
Correct |
16 ms |
1896 KB |
Output is correct |
17 |
Correct |
17 ms |
1884 KB |
Output is correct |
18 |
Correct |
1335 ms |
8680 KB |
Output is correct |
19 |
Correct |
1335 ms |
8296 KB |
Output is correct |
20 |
Correct |
1346 ms |
8196 KB |
Output is correct |
21 |
Correct |
1319 ms |
8476 KB |
Output is correct |
22 |
Correct |
1353 ms |
8560 KB |
Output is correct |
23 |
Correct |
1526 ms |
7476 KB |
Output is correct |
24 |
Correct |
1443 ms |
7536 KB |
Output is correct |
25 |
Correct |
1442 ms |
7800 KB |
Output is correct |
26 |
Correct |
40 ms |
3164 KB |
Output is correct |
27 |
Correct |
773 ms |
7688 KB |
Output is correct |
28 |
Correct |
780 ms |
7364 KB |
Output is correct |
29 |
Correct |
1199 ms |
6500 KB |
Output is correct |
30 |
Correct |
1207 ms |
7572 KB |
Output is correct |
31 |
Correct |
900 ms |
6996 KB |
Output is correct |
32 |
Correct |
439 ms |
4720 KB |
Output is correct |
33 |
Correct |
947 ms |
6896 KB |
Output is correct |
34 |
Correct |
930 ms |
6856 KB |
Output is correct |
35 |
Correct |
40 ms |
3156 KB |
Output is correct |
36 |
Correct |
911 ms |
7036 KB |
Output is correct |
37 |
Correct |
880 ms |
6684 KB |
Output is correct |
38 |
Correct |
846 ms |
6764 KB |
Output is correct |
39 |
Correct |
758 ms |
5716 KB |
Output is correct |
40 |
Correct |
742 ms |
5688 KB |
Output is correct |
41 |
Correct |
765 ms |
6984 KB |
Output is correct |
42 |
Correct |
741 ms |
7168 KB |
Output is correct |
43 |
Correct |
2365 ms |
8612 KB |
Output is correct |
44 |
Correct |
41 ms |
3152 KB |
Output is correct |
45 |
Correct |
225 ms |
5816 KB |
Output is correct |
46 |
Correct |
76 ms |
5940 KB |
Output is correct |
47 |
Correct |
1046 ms |
7152 KB |
Output is correct |
48 |
Correct |
2343 ms |
8868 KB |
Output is correct |
49 |
Correct |
1052 ms |
7352 KB |
Output is correct |
50 |
Correct |
1141 ms |
6120 KB |
Output is correct |
51 |
Correct |
1174 ms |
6340 KB |
Output is correct |
52 |
Correct |
1134 ms |
6104 KB |
Output is correct |
53 |
Correct |
1827 ms |
7708 KB |
Output is correct |
54 |
Correct |
1798 ms |
7540 KB |
Output is correct |
55 |
Correct |
1860 ms |
7516 KB |
Output is correct |
56 |
Correct |
904 ms |
7272 KB |
Output is correct |
57 |
Correct |
967 ms |
7260 KB |
Output is correct |
58 |
Correct |
2473 ms |
8668 KB |
Output is correct |
59 |
Correct |
2441 ms |
8584 KB |
Output is correct |
60 |
Correct |
2388 ms |
8736 KB |
Output is correct |
61 |
Correct |
2393 ms |
9324 KB |
Output is correct |
62 |
Correct |
2125 ms |
7896 KB |
Output is correct |
63 |
Correct |
2028 ms |
7736 KB |
Output is correct |
64 |
Correct |
2331 ms |
8580 KB |
Output is correct |
65 |
Correct |
1316 ms |
6628 KB |
Output is correct |
66 |
Correct |
1363 ms |
8208 KB |
Output is correct |
67 |
Correct |
1470 ms |
8548 KB |
Output is correct |
68 |
Correct |
1383 ms |
8220 KB |
Output is correct |
69 |
Correct |
1287 ms |
7948 KB |
Output is correct |
70 |
Correct |
1500 ms |
8292 KB |
Output is correct |
71 |
Correct |
1547 ms |
8224 KB |
Output is correct |
72 |
Correct |
1569 ms |
8260 KB |
Output is correct |
73 |
Correct |
1406 ms |
8128 KB |
Output is correct |
74 |
Correct |
1454 ms |
8108 KB |
Output is correct |
75 |
Correct |
1403 ms |
8256 KB |
Output is correct |
76 |
Correct |
1292 ms |
7916 KB |
Output is correct |
77 |
Correct |
1288 ms |
7948 KB |
Output is correct |
78 |
Correct |
1303 ms |
8160 KB |
Output is correct |
79 |
Correct |
1214 ms |
6880 KB |
Output is correct |
80 |
Correct |
1202 ms |
6860 KB |
Output is correct |
81 |
Correct |
1251 ms |
6860 KB |
Output is correct |
82 |
Correct |
1178 ms |
8368 KB |
Output is correct |
83 |
Correct |
1184 ms |
8596 KB |
Output is correct |
84 |
Correct |
1177 ms |
8520 KB |
Output is correct |
85 |
Correct |
2518 ms |
10088 KB |
Output is correct |
86 |
Correct |
242 ms |
6304 KB |
Output is correct |
87 |
Correct |
96 ms |
6904 KB |
Output is correct |
88 |
Correct |
1209 ms |
8676 KB |
Output is correct |
89 |
Correct |
2509 ms |
10244 KB |
Output is correct |
90 |
Correct |
1197 ms |
8516 KB |
Output is correct |
91 |
Correct |
1396 ms |
8080 KB |
Output is correct |
92 |
Correct |
1380 ms |
8172 KB |
Output is correct |
93 |
Correct |
1493 ms |
7720 KB |
Output is correct |
94 |
Correct |
2017 ms |
9180 KB |
Output is correct |
95 |
Correct |
2040 ms |
9460 KB |
Output is correct |
96 |
Correct |
2052 ms |
8384 KB |
Output is correct |
97 |
Correct |
1122 ms |
7432 KB |
Output is correct |
98 |
Correct |
1203 ms |
8684 KB |
Output is correct |
99 |
Correct |
2609 ms |
10032 KB |
Output is correct |
100 |
Correct |
2538 ms |
10072 KB |
Output is correct |
101 |
Correct |
2548 ms |
10220 KB |
Output is correct |
102 |
Correct |
2572 ms |
10216 KB |
Output is correct |
103 |
Correct |
2174 ms |
8912 KB |
Output is correct |
104 |
Correct |
2180 ms |
8648 KB |
Output is correct |
105 |
Correct |
2054 ms |
8488 KB |
Output is correct |
106 |
Correct |
1829 ms |
8404 KB |
Output is correct |
107 |
Correct |
2070 ms |
8588 KB |
Output is correct |
108 |
Correct |
2419 ms |
9512 KB |
Output is correct |
109 |
Correct |
1410 ms |
7720 KB |
Output is correct |