Submission #914623

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
914623	2024-01-22T12:15:23 Z	coding_monk3	Bridges (APIO19_bridges)	C++17	100 / 100	1523 ms	14984 KB

bridges

#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 = 1200;
    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);}
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1628 KB	Output is correct
2	Correct	1 ms	1624 KB	Output is correct
3	Correct	30 ms	3924 KB	Output is correct
4	Correct	5 ms	1628 KB	Output is correct
5	Correct	33 ms	2188 KB	Output is correct
6	Correct	22 ms	2196 KB	Output is correct
7	Correct	24 ms	2444 KB	Output is correct
8	Correct	29 ms	2140 KB	Output is correct
9	Correct	24 ms	2340 KB	Output is correct
10	Correct	27 ms	2140 KB	Output is correct
11	Correct	28 ms	2152 KB	Output is correct
12	Correct	28 ms	2280 KB	Output is correct
13	Correct	32 ms	2644 KB	Output is correct
14	Correct	37 ms	2540 KB	Output is correct
15	Correct	31 ms	2140 KB	Output is correct
16	Correct	25 ms	2288 KB	Output is correct
17	Correct	26 ms	2140 KB	Output is correct

Subtask #2

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1041 ms	9592 KB	Output is correct
2	Correct	1032 ms	9616 KB	Output is correct
3	Correct	1073 ms	9640 KB	Output is correct
4	Correct	1022 ms	9668 KB	Output is correct
5	Correct	1026 ms	9564 KB	Output is correct
6	Correct	1523 ms	8968 KB	Output is correct
7	Correct	1407 ms	8780 KB	Output is correct
8	Correct	1310 ms	8824 KB	Output is correct
9	Correct	40 ms	1880 KB	Output is correct
10	Correct	1069 ms	9572 KB	Output is correct
11	Correct	987 ms	9848 KB	Output is correct
12	Correct	793 ms	5332 KB	Output is correct
13	Correct	846 ms	13720 KB	Output is correct

Subtask #3

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	814 ms	8780 KB	Output is correct
2	Correct	706 ms	7248 KB	Output is correct
3	Correct	1026 ms	8696 KB	Output is correct
4	Correct	814 ms	9028 KB	Output is correct
5	Correct	43 ms	1772 KB	Output is correct
6	Correct	909 ms	8640 KB	Output is correct
7	Correct	772 ms	8900 KB	Output is correct
8	Correct	702 ms	8812 KB	Output is correct
9	Correct	518 ms	4436 KB	Output is correct
10	Correct	471 ms	4084 KB	Output is correct
11	Correct	557 ms	10508 KB	Output is correct
12	Correct	494 ms	9764 KB	Output is correct

Subtask #4

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1025 ms	5268 KB	Output is correct
2	Correct	41 ms	1752 KB	Output is correct
3	Correct	115 ms	3916 KB	Output is correct
4	Correct	53 ms	3924 KB	Output is correct
5	Correct	488 ms	4976 KB	Output is correct
6	Correct	1027 ms	4976 KB	Output is correct
7	Correct	476 ms	4892 KB	Output is correct
8	Correct	524 ms	3724 KB	Output is correct
9	Correct	509 ms	3472 KB	Output is correct
10	Correct	519 ms	3608 KB	Output is correct
11	Correct	839 ms	4420 KB	Output is correct
12	Correct	803 ms	4224 KB	Output is correct
13	Correct	821 ms	4500 KB	Output is correct
14	Correct	411 ms	4972 KB	Output is correct
15	Correct	487 ms	4876 KB	Output is correct
16	Correct	1084 ms	5024 KB	Output is correct
17	Correct	1076 ms	5312 KB	Output is correct
18	Correct	1049 ms	4936 KB	Output is correct
19	Correct	1112 ms	5028 KB	Output is correct
20	Correct	905 ms	4852 KB	Output is correct
21	Correct	923 ms	4792 KB	Output is correct
22	Correct	1027 ms	4724 KB	Output is correct
23	Correct	570 ms	4572 KB	Output is correct

Subtask #5

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1041 ms	9592 KB	Output is correct
2	Correct	1032 ms	9616 KB	Output is correct
3	Correct	1073 ms	9640 KB	Output is correct
4	Correct	1022 ms	9668 KB	Output is correct
5	Correct	1026 ms	9564 KB	Output is correct
6	Correct	1523 ms	8968 KB	Output is correct
7	Correct	1407 ms	8780 KB	Output is correct
8	Correct	1310 ms	8824 KB	Output is correct
9	Correct	40 ms	1880 KB	Output is correct
10	Correct	1069 ms	9572 KB	Output is correct
11	Correct	987 ms	9848 KB	Output is correct
12	Correct	793 ms	5332 KB	Output is correct
13	Correct	846 ms	13720 KB	Output is correct
14	Correct	814 ms	8780 KB	Output is correct
15	Correct	706 ms	7248 KB	Output is correct
16	Correct	1026 ms	8696 KB	Output is correct
17	Correct	814 ms	9028 KB	Output is correct
18	Correct	43 ms	1772 KB	Output is correct
19	Correct	909 ms	8640 KB	Output is correct
20	Correct	772 ms	8900 KB	Output is correct
21	Correct	702 ms	8812 KB	Output is correct
22	Correct	518 ms	4436 KB	Output is correct
23	Correct	471 ms	4084 KB	Output is correct
24	Correct	557 ms	10508 KB	Output is correct
25	Correct	494 ms	9764 KB	Output is correct
26	Correct	1044 ms	9492 KB	Output is correct
27	Correct	1255 ms	9616 KB	Output is correct
28	Correct	1070 ms	9592 KB	Output is correct
29	Correct	824 ms	9392 KB	Output is correct
30	Correct	1230 ms	9820 KB	Output is correct
31	Correct	1304 ms	9764 KB	Output is correct
32	Correct	1265 ms	9576 KB	Output is correct
33	Correct	1073 ms	9720 KB	Output is correct
34	Correct	1061 ms	9644 KB	Output is correct
35	Correct	1116 ms	9756 KB	Output is correct
36	Correct	867 ms	9472 KB	Output is correct
37	Correct	847 ms	9372 KB	Output is correct
38	Correct	847 ms	9332 KB	Output is correct
39	Correct	652 ms	4864 KB	Output is correct
40	Correct	635 ms	4924 KB	Output is correct
41	Correct	636 ms	4800 KB	Output is correct
42	Correct	626 ms	9496 KB	Output is correct
43	Correct	648 ms	9404 KB	Output is correct
44	Correct	637 ms	9580 KB	Output is correct

Subtask #6

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1628 KB	Output is correct
2	Correct	1 ms	1624 KB	Output is correct
3	Correct	30 ms	3924 KB	Output is correct
4	Correct	5 ms	1628 KB	Output is correct
5	Correct	33 ms	2188 KB	Output is correct
6	Correct	22 ms	2196 KB	Output is correct
7	Correct	24 ms	2444 KB	Output is correct
8	Correct	29 ms	2140 KB	Output is correct
9	Correct	24 ms	2340 KB	Output is correct
10	Correct	27 ms	2140 KB	Output is correct
11	Correct	28 ms	2152 KB	Output is correct
12	Correct	28 ms	2280 KB	Output is correct
13	Correct	32 ms	2644 KB	Output is correct
14	Correct	37 ms	2540 KB	Output is correct
15	Correct	31 ms	2140 KB	Output is correct
16	Correct	25 ms	2288 KB	Output is correct
17	Correct	26 ms	2140 KB	Output is correct
18	Correct	1041 ms	9592 KB	Output is correct
19	Correct	1032 ms	9616 KB	Output is correct
20	Correct	1073 ms	9640 KB	Output is correct
21	Correct	1022 ms	9668 KB	Output is correct
22	Correct	1026 ms	9564 KB	Output is correct
23	Correct	1523 ms	8968 KB	Output is correct
24	Correct	1407 ms	8780 KB	Output is correct
25	Correct	1310 ms	8824 KB	Output is correct
26	Correct	40 ms	1880 KB	Output is correct
27	Correct	1069 ms	9572 KB	Output is correct
28	Correct	987 ms	9848 KB	Output is correct
29	Correct	793 ms	5332 KB	Output is correct
30	Correct	846 ms	13720 KB	Output is correct
31	Correct	814 ms	8780 KB	Output is correct
32	Correct	706 ms	7248 KB	Output is correct
33	Correct	1026 ms	8696 KB	Output is correct
34	Correct	814 ms	9028 KB	Output is correct
35	Correct	43 ms	1772 KB	Output is correct
36	Correct	909 ms	8640 KB	Output is correct
37	Correct	772 ms	8900 KB	Output is correct
38	Correct	702 ms	8812 KB	Output is correct
39	Correct	518 ms	4436 KB	Output is correct
40	Correct	471 ms	4084 KB	Output is correct
41	Correct	557 ms	10508 KB	Output is correct
42	Correct	494 ms	9764 KB	Output is correct
43	Correct	1025 ms	5268 KB	Output is correct
44	Correct	41 ms	1752 KB	Output is correct
45	Correct	115 ms	3916 KB	Output is correct
46	Correct	53 ms	3924 KB	Output is correct
47	Correct	488 ms	4976 KB	Output is correct
48	Correct	1027 ms	4976 KB	Output is correct
49	Correct	476 ms	4892 KB	Output is correct
50	Correct	524 ms	3724 KB	Output is correct
51	Correct	509 ms	3472 KB	Output is correct
52	Correct	519 ms	3608 KB	Output is correct
53	Correct	839 ms	4420 KB	Output is correct
54	Correct	803 ms	4224 KB	Output is correct
55	Correct	821 ms	4500 KB	Output is correct
56	Correct	411 ms	4972 KB	Output is correct
57	Correct	487 ms	4876 KB	Output is correct
58	Correct	1084 ms	5024 KB	Output is correct
59	Correct	1076 ms	5312 KB	Output is correct
60	Correct	1049 ms	4936 KB	Output is correct
61	Correct	1112 ms	5028 KB	Output is correct
62	Correct	905 ms	4852 KB	Output is correct
63	Correct	923 ms	4792 KB	Output is correct
64	Correct	1027 ms	4724 KB	Output is correct
65	Correct	570 ms	4572 KB	Output is correct
66	Correct	1044 ms	9492 KB	Output is correct
67	Correct	1255 ms	9616 KB	Output is correct
68	Correct	1070 ms	9592 KB	Output is correct
69	Correct	824 ms	9392 KB	Output is correct
70	Correct	1230 ms	9820 KB	Output is correct
71	Correct	1304 ms	9764 KB	Output is correct
72	Correct	1265 ms	9576 KB	Output is correct
73	Correct	1073 ms	9720 KB	Output is correct
74	Correct	1061 ms	9644 KB	Output is correct
75	Correct	1116 ms	9756 KB	Output is correct
76	Correct	867 ms	9472 KB	Output is correct
77	Correct	847 ms	9372 KB	Output is correct
78	Correct	847 ms	9332 KB	Output is correct
79	Correct	652 ms	4864 KB	Output is correct
80	Correct	635 ms	4924 KB	Output is correct
81	Correct	636 ms	4800 KB	Output is correct
82	Correct	626 ms	9496 KB	Output is correct
83	Correct	648 ms	9404 KB	Output is correct
84	Correct	637 ms	9580 KB	Output is correct
85	Correct	1407 ms	10664 KB	Output is correct
86	Correct	154 ms	7448 KB	Output is correct
87	Correct	76 ms	8684 KB	Output is correct
88	Correct	808 ms	10612 KB	Output is correct
89	Correct	1415 ms	10492 KB	Output is correct
90	Correct	818 ms	10064 KB	Output is correct
91	Correct	1071 ms	9628 KB	Output is correct
92	Correct	1058 ms	9564 KB	Output is correct
93	Correct	1310 ms	8920 KB	Output is correct
94	Correct	1196 ms	10228 KB	Output is correct
95	Correct	1242 ms	10360 KB	Output is correct
96	Correct	1197 ms	9580 KB	Output is correct
97	Correct	613 ms	6368 KB	Output is correct
98	Correct	606 ms	14984 KB	Output is correct
99	Correct	1406 ms	10396 KB	Output is correct
100	Correct	1414 ms	10748 KB	Output is correct
101	Correct	1455 ms	10640 KB	Output is correct
102	Correct	1434 ms	10424 KB	Output is correct
103	Correct	1246 ms	9524 KB	Output is correct
104	Correct	1212 ms	9244 KB	Output is correct
105	Correct	1002 ms	13860 KB	Output is correct
106	Correct	868 ms	13640 KB	Output is correct
107	Correct	1012 ms	5912 KB	Output is correct
108	Correct	1333 ms	9864 KB	Output is correct
109	Correct	909 ms	9472 KB	Output is correct