oj.uz

Submission #252482

# Submission time Handle Problem Language Result Execution time Memory
252482 2020-07-25T16:38:39 Z rqi Duathlon (APIO18_duathlon) C++14
100 / 100
 507 ms 72928 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 

typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<db,db> pd; 

typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<db> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; 
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 

template<class T> bool ckmin(T& a, const T& b) { 
    return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
    return a < b ? a = b, 1 : 0; } 
template<class T> void remDup(vector<T>& v) { 
    sort(all(v)); v.erase(unique(all(v)),end(v)); }
int pct(int x) { return __builtin_popcount(x); } 
int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 
int fstTrue(function<bool(int)> f, int lo, int hi) {
    hi ++; assert(lo <= hi); // assuming f is increasing
    while (lo < hi) { // find first index such that f is true 
        int mid = (lo+hi)/2; 
        f(mid) ? hi = mid : lo = mid+1; 
    } 
    return lo;
}

// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);

template<class T> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }

template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }

// TO_STRING
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(bool b) { return b ? "true" : "false"; }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
template<class A> str ts(complex<A> c) { 
    stringstream ss; ss << c; return ss.str(); }
str ts(vector<bool> v) { 
    str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]);
    res += "}"; return res; }
template<size_t SZ> str ts(bitset<SZ> b) {
    str res = ""; F0R(i,SZ) res += char('0'+b[i]);
    return res; }
template<class A, class B> str ts(pair<A,B> p);
template<class T> str ts(T v) { // containers with begin(), end()
    bool fst = 1; str res = "{";
    for (const auto& x: v) {
        if (!fst) res += ", ";
        fst = 0; res += ts(x);
    }
    res += "}"; return res;
}
template<class A, class B> str ts(pair<A,B> p) {
    return "("+ts(p.f)+", "+ts(p.s)+")"; }

// OUTPUT
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) { 
    pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { 
    pr(h); if (sizeof...(t)) pr(" "); ps(t...); }

// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << ts(h); if (sizeof...(t)) cerr << ", ";
    DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif

// FILE I/O
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
void setIO(string s = "") {
    unsyncIO();
    // cin.exceptions(cin.failbit); 
    // throws exception when do smth illegal
    // ex. try to read letter into int
    if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

/**
 * Description: Biconnected components of edges. Removing any vertex in BCC
    * doesn't disconnect it. To get block-cut tree, create a bipartite graph
    * with the original vertices on the left and a vertex for each BCC on the right. 
    * Draw edge $u\leftrightarrow v$ if $u$ is contained within the BCC for $v$.
    * Self-loops are not included in any BCC while BCCS of size 1 represent
    * bridges.
 * Time: O(N+M)
 * Source: GeeksForGeeks (corrected)
 * Verification: 
    * USACO December 2017, Push a Box -> https://pastebin.com/yUWuzTH8
    * https://cses.fi/problemset/task/1705/
 */

struct BCC {
    vector<vpi> adj; vpi ed; 
    vector<vi> comps; // edges for each bcc
    int N, ti = 0; vi disc, st; 
    void init(int _N) { N = _N; disc.rsz(N), adj.rsz(N); }
    void ae(int x, int y) { 
        adj[x].eb(y,sz(ed)), adj[y].eb(x,sz(ed)), ed.eb(x,y); }
    int dfs(int x, int p = -1) { // return lowest disc
        int low = disc[x] = ++ti;
        trav(e,adj[x]) if (e.s != p) {
            if (!disc[e.f]) {
                st.pb(e.s); // disc[x] < LOW -> bridge
                int LOW = dfs(e.f,e.s); ckmin(low,LOW); 
                if (disc[x] <= LOW) { // get edges in bcc
                    comps.eb(); vi& tmp = comps.bk; // new bcc
                    for (int y = -1; y != e.s; )
                        tmp.pb(y = st.bk), st.pop_back();
                }
            } else if (disc[e.f] < disc[x]) // back-edge
                ckmin(low,disc[e.f]), st.pb(e.s);
        }
        return low;
    }
    void gen() { F0R(i,N) if (!disc[i]) dfs(i);  }
};


const int mx = 400005;
int n;
vi oadj[mx];
bool ovisited[mx];
vi olist;

void ogenList(int node){
    if(ovisited[node]) return;
    //dbg(node);
    ovisited[node] = 1;
    olist.pb(node);
    for(auto u: oadj[node]){
        ogenList(u);
    }
}

int N;
vi adj[mx];

vi cadj[mx]; //compnumber+N+1 vertices
int sub[mx];

void genSub(int node, int prv = -1){
    for(auto u: cadj[node]){
        if(u == prv) continue;
        genSub(u, node);
        sub[node]+=sub[u];
    }
    if(node <= N) sub[node]++;
}

ll hardSolve(){
    ll ans = 0;
    BCC bcc;
    bcc.init(N+1);
    for(int i = 1; i <= N; i++){
        for(auto u: adj[i]){
            if(u > i){
                bcc.ae(i, u);
            }
        }
    }
    bcc.gen();
    for(int i = 1; i <= sz(bcc.comps)-1+N+1; i++){
        cadj[i].clear();
        sub[i] = 0;
    }

    ans = ll(N)*ll(N-1)*ll(N-2);
    vector<vi> comps;

    //dbg(bcc.ed);
    for(int i = 0; i < sz(bcc.comps); i++){
        //dbg(i, bcc.comps[i]);
        comps.pb(vi{});
        for(auto u: bcc.comps[i]){
            comps.bk.pb(bcc.ed[u].f);
            comps.bk.pb(bcc.ed[u].s);
        }

        remDup(comps.bk);
        //dbg(i, comps.bk);
        for(auto u: comps.bk){
            cadj[i+N+1].pb(u);
            cadj[u].pb(i+N+1);
        }
    }

    // dbg(comps);
    // for(int i = 1; i <= sz(bcc.comps)+N; i++){
    //     dbg(i, cadj[i]);
    // }

    genSub(1);

    // for(int i = 1; i <= N+sz(comps); i++){
    //     dbg(i, sub[i]);
    // }
    for(int i = 0; i < sz(comps); i++){
        vi u = comps[i];
        for(auto x: u){
            ll tr = 0;
            if(sub[x] > sub[i+N+1]){
                tr = sub[1]-sub[i+N+1];
            }
            else{
                tr = sub[x];
            }
            //dbg(i+N+1, x, tr);
            ans-=ll(sz(u)-1)*ll(tr)*ll(tr-1);
        }
    }
    return ans;
}

ll solve(){
    return hardSolve();
}

int main() {
    setIO();
    int m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        oadj[u].pb(v);
        oadj[v].pb(u);
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        if(ovisited[i]) continue;
        //dbg(i);
        olist.clear();
        ogenList(i);
        map<int, int> m;
        for(int i = 0; i < sz(olist); i++){
            m[olist[i]] = i+1;
        }
        N = sz(olist);
        for(int i = 1; i <= N; i++){
            adj[i].clear();
        }
        for(auto u: olist){
            for(auto x: oadj[u]){
                adj[m[u]].pb(m[x]);
            }
        }
        ans+=solve();
    }
    ps(ans);
    // you should actually read the stuff at the bottom
}

/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
*/

Compilation message

count_triplets.cpp: In function 'void setIn(std::__cxx11::string)':
count_triplets.cpp:130:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void setOut(std::__cxx11::string)':
count_triplets.cpp:131:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28544 KB Output is correct
2 Correct 17 ms 28588 KB Output is correct
3 Correct 17 ms 28544 KB Output is correct
4 Correct 17 ms 28544 KB Output is correct
5 Correct 17 ms 28544 KB Output is correct
6 Correct 17 ms 28544 KB Output is correct
7 Correct 16 ms 28544 KB Output is correct
8 Correct 17 ms 28544 KB Output is correct
9 Correct 18 ms 28544 KB Output is correct
10 Correct 16 ms 28544 KB Output is correct
11 Correct 17 ms 28544 KB Output is correct
12 Correct 17 ms 28544 KB Output is correct
13 Correct 17 ms 28544 KB Output is correct
14 Correct 16 ms 28544 KB Output is correct
15 Correct 17 ms 28544 KB Output is correct
16 Correct 16 ms 28544 KB Output is correct
17 Correct 17 ms 28544 KB Output is correct
18 Correct 17 ms 28544 KB Output is correct
19 Correct 17 ms 28544 KB Output is correct
20 Correct 16 ms 28544 KB Output is correct
21 Correct 17 ms 28544 KB Output is correct
22 Correct 16 ms 28544 KB Output is correct
23 Correct 16 ms 28544 KB Output is correct
24 Correct 18 ms 28544 KB Output is correct
25 Correct 17 ms 28544 KB Output is correct
26 Correct 16 ms 28488 KB Output is correct
27 Correct 16 ms 28544 KB Output is correct
28 Correct 16 ms 28544 KB Output is correct
29 Correct 17 ms 28544 KB Output is correct
30 Correct 16 ms 28544 KB Output is correct
31 Correct 17 ms 28544 KB Output is correct
32 Correct 17 ms 28544 KB Output is correct
33 Correct 16 ms 28544 KB Output is correct
34 Correct 16 ms 28536 KB Output is correct
35 Correct 17 ms 28544 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28544 KB Output is correct
2 Correct 17 ms 28588 KB Output is correct
3 Correct 17 ms 28544 KB Output is correct
4 Correct 17 ms 28544 KB Output is correct
5 Correct 17 ms 28544 KB Output is correct
6 Correct 17 ms 28544 KB Output is correct
7 Correct 16 ms 28544 KB Output is correct
8 Correct 17 ms 28544 KB Output is correct
9 Correct 18 ms 28544 KB Output is correct
10 Correct 16 ms 28544 KB Output is correct
11 Correct 17 ms 28544 KB Output is correct
12 Correct 17 ms 28544 KB Output is correct
13 Correct 17 ms 28544 KB Output is correct
14 Correct 16 ms 28544 KB Output is correct
15 Correct 17 ms 28544 KB Output is correct
16 Correct 16 ms 28544 KB Output is correct
17 Correct 17 ms 28544 KB Output is correct
18 Correct 17 ms 28544 KB Output is correct
19 Correct 17 ms 28544 KB Output is correct
20 Correct 16 ms 28544 KB Output is correct
21 Correct 17 ms 28544 KB Output is correct
22 Correct 16 ms 28544 KB Output is correct
23 Correct 16 ms 28544 KB Output is correct
24 Correct 18 ms 28544 KB Output is correct
25 Correct 17 ms 28544 KB Output is correct
26 Correct 16 ms 28488 KB Output is correct
27 Correct 16 ms 28544 KB Output is correct
28 Correct 16 ms 28544 KB Output is correct
29 Correct 17 ms 28544 KB Output is correct
30 Correct 16 ms 28544 KB Output is correct
31 Correct 17 ms 28544 KB Output is correct
32 Correct 17 ms 28544 KB Output is correct
33 Correct 16 ms 28544 KB Output is correct
34 Correct 16 ms 28536 KB Output is correct
35 Correct 17 ms 28544 KB Output is correct
36 Correct 16 ms 28544 KB Output is correct
37 Correct 17 ms 28544 KB Output is correct
38 Correct 17 ms 28544 KB Output is correct
39 Correct 18 ms 28544 KB Output is correct
40 Correct 17 ms 28544 KB Output is correct
41 Correct 16 ms 28544 KB Output is correct
42 Correct 17 ms 28544 KB Output is correct
43 Correct 16 ms 28544 KB Output is correct
44 Correct 17 ms 28544 KB Output is correct
45 Correct 18 ms 28544 KB Output is correct
46 Correct 17 ms 28544 KB Output is correct
47 Correct 16 ms 28544 KB Output is correct
48 Correct 16 ms 28544 KB Output is correct
49 Correct 17 ms 28544 KB Output is correct
50 Correct 17 ms 28544 KB Output is correct
51 Correct 23 ms 28544 KB Output is correct
52 Correct 16 ms 28544 KB Output is correct
53 Correct 16 ms 28544 KB Output is correct
54 Correct 16 ms 28544 KB Output is correct
55 Correct 17 ms 28544 KB Output is correct
56 Correct 17 ms 28544 KB Output is correct
57 Correct 17 ms 28544 KB Output is correct
58 Correct 16 ms 28544 KB Output is correct
59 Correct 17 ms 28544 KB Output is correct
60 Correct 17 ms 28544 KB Output is correct
61 Correct 16 ms 28544 KB Output is correct
62 Correct 16 ms 28544 KB Output is correct
63 Correct 17 ms 28544 KB Output is correct
64 Correct 20 ms 28672 KB Output is correct
65 Correct 17 ms 28544 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 59628 KB Output is correct
2 Correct 239 ms 59628 KB Output is correct
3 Correct 236 ms 54036 KB Output is correct
4 Correct 218 ms 53616 KB Output is correct
5 Correct 206 ms 48196 KB Output is correct
6 Correct 232 ms 55384 KB Output is correct
7 Correct 196 ms 42260 KB Output is correct
8 Correct 211 ms 48104 KB Output is correct
9 Correct 202 ms 37980 KB Output is correct
10 Correct 189 ms 40576 KB Output is correct
11 Correct 118 ms 32632 KB Output is correct
12 Correct 118 ms 32632 KB Output is correct
13 Correct 111 ms 32524 KB Output is correct
14 Correct 107 ms 32376 KB Output is correct
15 Correct 100 ms 31864 KB Output is correct
16 Correct 88 ms 31736 KB Output is correct
17 Correct 37 ms 28672 KB Output is correct
18 Correct 35 ms 28672 KB Output is correct
19 Correct 35 ms 28672 KB Output is correct
20 Correct 36 ms 28672 KB Output is correct
21 Correct 35 ms 28672 KB Output is correct
22 Correct 35 ms 28672 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28928 KB Output is correct
2 Correct 18 ms 28928 KB Output is correct
3 Correct 18 ms 28928 KB Output is correct
4 Correct 18 ms 28928 KB Output is correct
5 Correct 22 ms 28916 KB Output is correct
6 Correct 18 ms 28928 KB Output is correct
7 Correct 25 ms 28992 KB Output is correct
8 Correct 19 ms 28928 KB Output is correct
9 Correct 24 ms 28928 KB Output is correct
10 Correct 24 ms 28928 KB Output is correct
11 Correct 18 ms 28800 KB Output is correct
12 Correct 24 ms 28800 KB Output is correct
13 Correct 17 ms 28672 KB Output is correct
14 Correct 18 ms 28544 KB Output is correct
15 Correct 17 ms 28544 KB Output is correct
16 Correct 17 ms 28620 KB Output is correct
17 Correct 19 ms 28928 KB Output is correct
18 Correct 17 ms 28928 KB Output is correct
19 Correct 18 ms 28928 KB Output is correct
20 Correct 22 ms 28928 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 65604 KB Output is correct
2 Correct 262 ms 66532 KB Output is correct
3 Correct 310 ms 66656 KB Output is correct
4 Correct 286 ms 66528 KB Output is correct
5 Correct 278 ms 66532 KB Output is correct
6 Correct 276 ms 72928 KB Output is correct
7 Correct 279 ms 70756 KB Output is correct
8 Correct 283 ms 69604 KB Output is correct
9 Correct 265 ms 68448 KB Output is correct
10 Correct 243 ms 51944 KB Output is correct
11 Correct 289 ms 62564 KB Output is correct
12 Correct 223 ms 43520 KB Output is correct
13 Correct 212 ms 41732 KB Output is correct
14 Correct 135 ms 32828 KB Output is correct
15 Correct 122 ms 32632 KB Output is correct
16 Correct 86 ms 31608 KB Output is correct
17 Correct 213 ms 67680 KB Output is correct
18 Correct 216 ms 67820 KB Output is correct
19 Correct 214 ms 67672 KB Output is correct
20 Correct 217 ms 67684 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28928 KB Output is correct
2 Correct 18 ms 28928 KB Output is correct
3 Correct 18 ms 28928 KB Output is correct
4 Correct 19 ms 28800 KB Output is correct
5 Correct 18 ms 28800 KB Output is correct
6 Correct 18 ms 28800 KB Output is correct
7 Correct 20 ms 28800 KB Output is correct
8 Correct 19 ms 28800 KB Output is correct
9 Correct 18 ms 28800 KB Output is correct
10 Correct 19 ms 28928 KB Output is correct
11 Correct 24 ms 28800 KB Output is correct
12 Correct 26 ms 28920 KB Output is correct
13 Correct 19 ms 28928 KB Output is correct
14 Correct 21 ms 28920 KB Output is correct
15 Correct 25 ms 28884 KB Output is correct
16 Correct 18 ms 28800 KB Output is correct
17 Correct 19 ms 28800 KB Output is correct
18 Correct 18 ms 28672 KB Output is correct
19 Correct 19 ms 28544 KB Output is correct
20 Correct 24 ms 28544 KB Output is correct
21 Correct 25 ms 28928 KB Output is correct
22 Correct 18 ms 28928 KB Output is correct
23 Correct 18 ms 28928 KB Output is correct
24 Correct 18 ms 28928 KB Output is correct
25 Correct 17 ms 28544 KB Output is correct
26 Correct 17 ms 28544 KB Output is correct
27 Correct 17 ms 28544 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 65760 KB Output is correct
2 Correct 270 ms 66280 KB Output is correct
3 Correct 277 ms 64356 KB Output is correct
4 Correct 277 ms 61928 KB Output is correct
5 Correct 258 ms 58988 KB Output is correct
6 Correct 256 ms 57196 KB Output is correct
7 Correct 244 ms 56428 KB Output is correct
8 Correct 235 ms 55404 KB Output is correct
9 Correct 249 ms 55236 KB Output is correct
10 Correct 231 ms 54892 KB Output is correct
11 Correct 233 ms 54380 KB Output is correct
12 Correct 221 ms 53936 KB Output is correct
13 Correct 249 ms 53956 KB Output is correct
14 Correct 260 ms 55404 KB Output is correct
15 Correct 331 ms 69604 KB Output is correct
16 Correct 316 ms 67996 KB Output is correct
17 Correct 336 ms 68324 KB Output is correct
18 Correct 309 ms 66836 KB Output is correct
19 Correct 322 ms 60268 KB Output is correct
20 Correct 298 ms 50116 KB Output is correct
21 Correct 304 ms 43180 KB Output is correct
22 Correct 171 ms 33108 KB Output is correct
23 Correct 136 ms 32888 KB Output is correct
24 Correct 335 ms 65420 KB Output is correct
25 Correct 313 ms 65504 KB Output is correct
26 Correct 312 ms 64484 KB Output is correct
27 Correct 300 ms 64460 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28544 KB Output is correct
2 Correct 17 ms 28588 KB Output is correct
3 Correct 17 ms 28544 KB Output is correct
4 Correct 17 ms 28544 KB Output is correct
5 Correct 17 ms 28544 KB Output is correct
6 Correct 17 ms 28544 KB Output is correct
7 Correct 16 ms 28544 KB Output is correct
8 Correct 17 ms 28544 KB Output is correct
9 Correct 18 ms 28544 KB Output is correct
10 Correct 16 ms 28544 KB Output is correct
11 Correct 17 ms 28544 KB Output is correct
12 Correct 17 ms 28544 KB Output is correct
13 Correct 17 ms 28544 KB Output is correct
14 Correct 16 ms 28544 KB Output is correct
15 Correct 17 ms 28544 KB Output is correct
16 Correct 16 ms 28544 KB Output is correct
17 Correct 17 ms 28544 KB Output is correct
18 Correct 17 ms 28544 KB Output is correct
19 Correct 17 ms 28544 KB Output is correct
20 Correct 16 ms 28544 KB Output is correct
21 Correct 17 ms 28544 KB Output is correct
22 Correct 16 ms 28544 KB Output is correct
23 Correct 16 ms 28544 KB Output is correct
24 Correct 18 ms 28544 KB Output is correct
25 Correct 17 ms 28544 KB Output is correct
26 Correct 16 ms 28488 KB Output is correct
27 Correct 16 ms 28544 KB Output is correct
28 Correct 16 ms 28544 KB Output is correct
29 Correct 17 ms 28544 KB Output is correct
30 Correct 16 ms 28544 KB Output is correct
31 Correct 17 ms 28544 KB Output is correct
32 Correct 17 ms 28544 KB Output is correct
33 Correct 16 ms 28544 KB Output is correct
34 Correct 16 ms 28536 KB Output is correct
35 Correct 17 ms 28544 KB Output is correct
36 Correct 16 ms 28544 KB Output is correct
37 Correct 17 ms 28544 KB Output is correct
38 Correct 17 ms 28544 KB Output is correct
39 Correct 18 ms 28544 KB Output is correct
40 Correct 17 ms 28544 KB Output is correct
41 Correct 16 ms 28544 KB Output is correct
42 Correct 17 ms 28544 KB Output is correct
43 Correct 16 ms 28544 KB Output is correct
44 Correct 17 ms 28544 KB Output is correct
45 Correct 18 ms 28544 KB Output is correct
46 Correct 17 ms 28544 KB Output is correct
47 Correct 16 ms 28544 KB Output is correct
48 Correct 16 ms 28544 KB Output is correct
49 Correct 17 ms 28544 KB Output is correct
50 Correct 17 ms 28544 KB Output is correct
51 Correct 23 ms 28544 KB Output is correct
52 Correct 16 ms 28544 KB Output is correct
53 Correct 16 ms 28544 KB Output is correct
54 Correct 16 ms 28544 KB Output is correct
55 Correct 17 ms 28544 KB Output is correct
56 Correct 17 ms 28544 KB Output is correct
57 Correct 17 ms 28544 KB Output is correct
58 Correct 16 ms 28544 KB Output is correct
59 Correct 17 ms 28544 KB Output is correct
60 Correct 17 ms 28544 KB Output is correct
61 Correct 16 ms 28544 KB Output is correct
62 Correct 16 ms 28544 KB Output is correct
63 Correct 17 ms 28544 KB Output is correct
64 Correct 20 ms 28672 KB Output is correct
65 Correct 17 ms 28544 KB Output is correct
66 Correct 15 ms 28572 KB Output is correct
67 Correct 17 ms 28544 KB Output is correct
68 Correct 16 ms 28800 KB Output is correct
69 Correct 23 ms 28792 KB Output is correct
70 Correct 18 ms 28928 KB Output is correct
71 Correct 17 ms 28544 KB Output is correct
72 Correct 16 ms 28544 KB Output is correct
73 Correct 17 ms 28544 KB Output is correct
74 Correct 16 ms 28544 KB Output is correct
75 Correct 17 ms 28544 KB Output is correct
76 Correct 15 ms 28544 KB Output is correct
77 Correct 21 ms 28928 KB Output is correct
78 Correct 17 ms 28800 KB Output is correct
79 Correct 18 ms 28800 KB Output is correct
80 Correct 19 ms 28800 KB Output is correct
81 Correct 19 ms 28724 KB Output is correct
82 Correct 17 ms 28800 KB Output is correct
83 Correct 17 ms 28800 KB Output is correct
84 Correct 18 ms 28800 KB Output is correct
85 Correct 19 ms 28792 KB Output is correct
86 Correct 17 ms 28800 KB Output is correct
87 Correct 17 ms 28672 KB Output is correct
88 Correct 17 ms 28672 KB Output is correct
89 Correct 16 ms 28544 KB Output is correct
90 Correct 16 ms 28544 KB Output is correct
91 Correct 23 ms 28800 KB Output is correct
92 Correct 18 ms 28800 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28544 KB Output is correct
2 Correct 17 ms 28588 KB Output is correct
3 Correct 17 ms 28544 KB Output is correct
4 Correct 17 ms 28544 KB Output is correct
5 Correct 17 ms 28544 KB Output is correct
6 Correct 17 ms 28544 KB Output is correct
7 Correct 16 ms 28544 KB Output is correct
8 Correct 17 ms 28544 KB Output is correct
9 Correct 18 ms 28544 KB Output is correct
10 Correct 16 ms 28544 KB Output is correct
11 Correct 17 ms 28544 KB Output is correct
12 Correct 17 ms 28544 KB Output is correct
13 Correct 17 ms 28544 KB Output is correct
14 Correct 16 ms 28544 KB Output is correct
15 Correct 17 ms 28544 KB Output is correct
16 Correct 16 ms 28544 KB Output is correct
17 Correct 17 ms 28544 KB Output is correct
18 Correct 17 ms 28544 KB Output is correct
19 Correct 17 ms 28544 KB Output is correct
20 Correct 16 ms 28544 KB Output is correct
21 Correct 17 ms 28544 KB Output is correct
22 Correct 16 ms 28544 KB Output is correct
23 Correct 16 ms 28544 KB Output is correct
24 Correct 18 ms 28544 KB Output is correct
25 Correct 17 ms 28544 KB Output is correct
26 Correct 16 ms 28488 KB Output is correct
27 Correct 16 ms 28544 KB Output is correct
28 Correct 16 ms 28544 KB Output is correct
29 Correct 17 ms 28544 KB Output is correct
30 Correct 16 ms 28544 KB Output is correct
31 Correct 17 ms 28544 KB Output is correct
32 Correct 17 ms 28544 KB Output is correct
33 Correct 16 ms 28544 KB Output is correct
34 Correct 16 ms 28536 KB Output is correct
35 Correct 17 ms 28544 KB Output is correct
36 Correct 16 ms 28544 KB Output is correct
37 Correct 17 ms 28544 KB Output is correct
38 Correct 17 ms 28544 KB Output is correct
39 Correct 18 ms 28544 KB Output is correct
40 Correct 17 ms 28544 KB Output is correct
41 Correct 16 ms 28544 KB Output is correct
42 Correct 17 ms 28544 KB Output is correct
43 Correct 16 ms 28544 KB Output is correct
44 Correct 17 ms 28544 KB Output is correct
45 Correct 18 ms 28544 KB Output is correct
46 Correct 17 ms 28544 KB Output is correct
47 Correct 16 ms 28544 KB Output is correct
48 Correct 16 ms 28544 KB Output is correct
49 Correct 17 ms 28544 KB Output is correct
50 Correct 17 ms 28544 KB Output is correct
51 Correct 23 ms 28544 KB Output is correct
52 Correct 16 ms 28544 KB Output is correct
53 Correct 16 ms 28544 KB Output is correct
54 Correct 16 ms 28544 KB Output is correct
55 Correct 17 ms 28544 KB Output is correct
56 Correct 17 ms 28544 KB Output is correct
57 Correct 17 ms 28544 KB Output is correct
58 Correct 16 ms 28544 KB Output is correct
59 Correct 17 ms 28544 KB Output is correct
60 Correct 17 ms 28544 KB Output is correct
61 Correct 16 ms 28544 KB Output is correct
62 Correct 16 ms 28544 KB Output is correct
63 Correct 17 ms 28544 KB Output is correct
64 Correct 20 ms 28672 KB Output is correct
65 Correct 17 ms 28544 KB Output is correct
66 Correct 234 ms 59628 KB Output is correct
67 Correct 239 ms 59628 KB Output is correct
68 Correct 236 ms 54036 KB Output is correct
69 Correct 218 ms 53616 KB Output is correct
70 Correct 206 ms 48196 KB Output is correct
71 Correct 232 ms 55384 KB Output is correct
72 Correct 196 ms 42260 KB Output is correct
73 Correct 211 ms 48104 KB Output is correct
74 Correct 202 ms 37980 KB Output is correct
75 Correct 189 ms 40576 KB Output is correct
76 Correct 118 ms 32632 KB Output is correct
77 Correct 118 ms 32632 KB Output is correct
78 Correct 111 ms 32524 KB Output is correct
79 Correct 107 ms 32376 KB Output is correct
80 Correct 100 ms 31864 KB Output is correct
81 Correct 88 ms 31736 KB Output is correct
82 Correct 37 ms 28672 KB Output is correct
83 Correct 35 ms 28672 KB Output is correct
84 Correct 35 ms 28672 KB Output is correct
85 Correct 36 ms 28672 KB Output is correct
86 Correct 35 ms 28672 KB Output is correct
87 Correct 35 ms 28672 KB Output is correct
88 Correct 18 ms 28928 KB Output is correct
89 Correct 18 ms 28928 KB Output is correct
90 Correct 18 ms 28928 KB Output is correct
91 Correct 18 ms 28928 KB Output is correct
92 Correct 22 ms 28916 KB Output is correct
93 Correct 18 ms 28928 KB Output is correct
94 Correct 25 ms 28992 KB Output is correct
95 Correct 19 ms 28928 KB Output is correct
96 Correct 24 ms 28928 KB Output is correct
97 Correct 24 ms 28928 KB Output is correct
98 Correct 18 ms 28800 KB Output is correct
99 Correct 24 ms 28800 KB Output is correct
100 Correct 17 ms 28672 KB Output is correct
101 Correct 18 ms 28544 KB Output is correct
102 Correct 17 ms 28544 KB Output is correct
103 Correct 17 ms 28620 KB Output is correct
104 Correct 19 ms 28928 KB Output is correct
105 Correct 17 ms 28928 KB Output is correct
106 Correct 18 ms 28928 KB Output is correct
107 Correct 22 ms 28928 KB Output is correct
108 Correct 282 ms 65604 KB Output is correct
109 Correct 262 ms 66532 KB Output is correct
110 Correct 310 ms 66656 KB Output is correct
111 Correct 286 ms 66528 KB Output is correct
112 Correct 278 ms 66532 KB Output is correct
113 Correct 276 ms 72928 KB Output is correct
114 Correct 279 ms 70756 KB Output is correct
115 Correct 283 ms 69604 KB Output is correct
116 Correct 265 ms 68448 KB Output is correct
117 Correct 243 ms 51944 KB Output is correct
118 Correct 289 ms 62564 KB Output is correct
119 Correct 223 ms 43520 KB Output is correct
120 Correct 212 ms 41732 KB Output is correct
121 Correct 135 ms 32828 KB Output is correct
122 Correct 122 ms 32632 KB Output is correct
123 Correct 86 ms 31608 KB Output is correct
124 Correct 213 ms 67680 KB Output is correct
125 Correct 216 ms 67820 KB Output is correct
126 Correct 214 ms 67672 KB Output is correct
127 Correct 217 ms 67684 KB Output is correct
128 Correct 18 ms 28928 KB Output is correct
129 Correct 18 ms 28928 KB Output is correct
130 Correct 18 ms 28928 KB Output is correct
131 Correct 19 ms 28800 KB Output is correct
132 Correct 18 ms 28800 KB Output is correct
133 Correct 18 ms 28800 KB Output is correct
134 Correct 20 ms 28800 KB Output is correct
135 Correct 19 ms 28800 KB Output is correct
136 Correct 18 ms 28800 KB Output is correct
137 Correct 19 ms 28928 KB Output is correct
138 Correct 24 ms 28800 KB Output is correct
139 Correct 26 ms 28920 KB Output is correct
140 Correct 19 ms 28928 KB Output is correct
141 Correct 21 ms 28920 KB Output is correct
142 Correct 25 ms 28884 KB Output is correct
143 Correct 18 ms 28800 KB Output is correct
144 Correct 19 ms 28800 KB Output is correct
145 Correct 18 ms 28672 KB Output is correct
146 Correct 19 ms 28544 KB Output is correct
147 Correct 24 ms 28544 KB Output is correct
148 Correct 25 ms 28928 KB Output is correct
149 Correct 18 ms 28928 KB Output is correct
150 Correct 18 ms 28928 KB Output is correct
151 Correct 18 ms 28928 KB Output is correct
152 Correct 17 ms 28544 KB Output is correct
153 Correct 17 ms 28544 KB Output is correct
154 Correct 17 ms 28544 KB Output is correct
155 Correct 270 ms 65760 KB Output is correct
156 Correct 270 ms 66280 KB Output is correct
157 Correct 277 ms 64356 KB Output is correct
158 Correct 277 ms 61928 KB Output is correct
159 Correct 258 ms 58988 KB Output is correct
160 Correct 256 ms 57196 KB Output is correct
161 Correct 244 ms 56428 KB Output is correct
162 Correct 235 ms 55404 KB Output is correct
163 Correct 249 ms 55236 KB Output is correct
164 Correct 231 ms 54892 KB Output is correct
165 Correct 233 ms 54380 KB Output is correct
166 Correct 221 ms 53936 KB Output is correct
167 Correct 249 ms 53956 KB Output is correct
168 Correct 260 ms 55404 KB Output is correct
169 Correct 331 ms 69604 KB Output is correct
170 Correct 316 ms 67996 KB Output is correct
171 Correct 336 ms 68324 KB Output is correct
172 Correct 309 ms 66836 KB Output is correct
173 Correct 322 ms 60268 KB Output is correct
174 Correct 298 ms 50116 KB Output is correct
175 Correct 304 ms 43180 KB Output is correct
176 Correct 171 ms 33108 KB Output is correct
177 Correct 136 ms 32888 KB Output is correct
178 Correct 335 ms 65420 KB Output is correct
179 Correct 313 ms 65504 KB Output is correct
180 Correct 312 ms 64484 KB Output is correct
181 Correct 300 ms 64460 KB Output is correct
182 Correct 15 ms 28572 KB Output is correct
183 Correct 17 ms 28544 KB Output is correct
184 Correct 16 ms 28800 KB Output is correct
185 Correct 23 ms 28792 KB Output is correct
186 Correct 18 ms 28928 KB Output is correct
187 Correct 17 ms 28544 KB Output is correct
188 Correct 16 ms 28544 KB Output is correct
189 Correct 17 ms 28544 KB Output is correct
190 Correct 16 ms 28544 KB Output is correct
191 Correct 17 ms 28544 KB Output is correct
192 Correct 15 ms 28544 KB Output is correct
193 Correct 21 ms 28928 KB Output is correct
194 Correct 17 ms 28800 KB Output is correct
195 Correct 18 ms 28800 KB Output is correct
196 Correct 19 ms 28800 KB Output is correct
197 Correct 19 ms 28724 KB Output is correct
198 Correct 17 ms 28800 KB Output is correct
199 Correct 17 ms 28800 KB Output is correct
200 Correct 18 ms 28800 KB Output is correct
201 Correct 19 ms 28792 KB Output is correct
202 Correct 17 ms 28800 KB Output is correct
203 Correct 17 ms 28672 KB Output is correct
204 Correct 17 ms 28672 KB Output is correct
205 Correct 16 ms 28544 KB Output is correct
206 Correct 16 ms 28544 KB Output is correct
207 Correct 23 ms 28800 KB Output is correct
208 Correct 18 ms 28800 KB Output is correct
209 Correct 35 ms 28664 KB Output is correct
210 Correct 105 ms 33160 KB Output is correct
211 Correct 267 ms 56316 KB Output is correct
212 Correct 352 ms 61804 KB Output is correct
213 Correct 507 ms 65640 KB Output is correct
214 Correct 118 ms 33144 KB Output is correct
215 Correct 128 ms 33272 KB Output is correct
216 Correct 311 ms 65480 KB Output is correct
217 Correct 331 ms 60140 KB Output is correct
218 Correct 302 ms 55660 KB Output is correct
219 Correct 284 ms 54656 KB Output is correct
220 Correct 248 ms 54508 KB Output is correct
221 Correct 229 ms 53868 KB Output is correct
222 Correct 242 ms 54380 KB Output is correct
223 Correct 338 ms 61928 KB Output is correct
224 Correct 306 ms 61036 KB Output is correct
225 Correct 303 ms 50896 KB Output is correct
226 Correct 269 ms 44308 KB Output is correct
227 Correct 269 ms 44144 KB Output is correct
228 Correct 158 ms 33400 KB Output is correct
229 Correct 133 ms 33144 KB Output is correct
230 Correct 292 ms 60152 KB Output is correct
231 Correct 335 ms 60264 KB Output is correct