oj.uz

Submission #587050

# Submission time Handle Problem Language Result Execution time Memory
587050 2022-07-01T09:16:23 Z MohamedFaresNebili Tropical Garden (IOI11_garden) C++14
100 / 100
 2676 ms 37404 KB 
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
 
                using namespace std;
 
                using ll = long long;
                using ii = pair<ll, ll>;
                using vi = vector<int>;
 
                #define ff first
                #define ss second
                #define pb push_back
                #define all(x) (x).begin(), (x).end()
                #define lb lower_bound
 
                const int oo = 1000 * 1000 * 1000 + 7;
 
                int C[2], to[300005], D[300005], DD[300005];
                int vis[300005], Vis[300005];
                vector<int> adj[300005], E[300005];
 
                void solve(int v) {
                    queue<int> Q; Q.push(v); D[v] = 0; int u = v;
                    while(vis[u] == 0) {
                        vis[u] = 1; u = to[u];
                    }
                    while(vis[u] != 2) {
                        vis[u] = 2; u = to[u]; C[0]++;
                    }
                    if(vis[v] != 2) C[0] = -1;
 
                    while(!Q.empty()) {
                        int A = Q.front(); Q.pop();
                        for(auto e : adj[A]) {
                            if(D[e] <= D[A] + 1) continue;
                            D[e] = D[A] + 1; Q.push(e);
                        }
                    }
 
                }
                void Solve(int v) {
                    queue<int> Q; Q.push(v); DD[v] = 0; int u = v;
                    while(Vis[u] == 0) {
                        Vis[u] = 1; u = to[u];
                    }
                    while(Vis[u] != 2) {
                        Vis[u] = 2; u = to[u]; C[1]++;
                    }
                    if(Vis[v] != 2) C[1] = -1;
 
                    while(!Q.empty()) {
                        int A = Q.front(); Q.pop();
                        for(auto e : adj[A]) {
                            if(DD[e] <= DD[A] + 1) continue;
                            DD[e] = DD[A] + 1; Q.push(e);
                        }
                    }
                }
 
                void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
                    memset(to, -1, sizeof to);
                    fill(D, D + 2 * N, oo); fill(DD, DD + 2 * N, oo);
 
                    for(int l = 0; l < M; l++) {
                        int U = R[l][0], V = R[l][1];
                        if(E[U].size() < 2) E[U].pb(V);
                        if(E[V].size() < 2) E[V].pb(U);
                    }
 
                    for(int l = 0; l < N; l++) {
                        D[l] = DD[l] = oo;
                        for(int i = 0; i < E[l].size(); i++) {
                            int U = E[l][i];
                            if(i == 0) {
                                to[l] = U;
                                if(E[U][0] == l && E[U].size() > 1)
                                    to[l] = U + N, U += N;
                                adj[U].pb(l);
                                continue;
                            }
                            to[l + N] = U;
                            if(E[U][0] == l && E[U].size() > 1)
                                to[l + N] = U + N, U += N;
                            adj[U].pb(l + N);
                        }
                    }
 
                    solve(P); Solve(P + N);
 
                    for(int l = 0; l < Q; l++) {
                        int T = G[l]; int res = 0;
                        for(int i = 0; i < N; i++) {
                            if(C[0] == -1 && D[i] == T) res++;
                            else if(C[0] > 0 && T >= D[i] && (T - D[i]) % C[0] == 0) res++;
                            else if(C[1] == -1 & DD[i] == T) res++;
                            else if(C[1] > 0 && T >= DD[i] && (T - DD[i]) % C[1] == 0) res++;
                        }
                        answer(res);
                    }
                }

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:76:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |                         for(int i = 0; i < E[l].size(); i++) {
      |                                        ~~^~~~~~~~~~~~~
garden.cpp:99:42: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   99 |                             else if(C[1] == -1 & DD[i] == T) res++;
      |                                     ~~~~~^~~~~

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15700 KB Output is correct
2 Correct 9 ms 15700 KB Output is correct
3 Correct 9 ms 15700 KB Output is correct
4 Correct 8 ms 15556 KB Output is correct
5 Correct 8 ms 15572 KB Output is correct
6 Correct 9 ms 15700 KB Output is correct
7 Correct 7 ms 15572 KB Output is correct
8 Correct 8 ms 15640 KB Output is correct
9 Correct 10 ms 15808 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15700 KB Output is correct
2 Correct 9 ms 15700 KB Output is correct
3 Correct 9 ms 15700 KB Output is correct
4 Correct 8 ms 15556 KB Output is correct
5 Correct 8 ms 15572 KB Output is correct
6 Correct 9 ms 15700 KB Output is correct
7 Correct 7 ms 15572 KB Output is correct
8 Correct 8 ms 15640 KB Output is correct
9 Correct 10 ms 15808 KB Output is correct
10 Correct 8 ms 15572 KB Output is correct
11 Correct 17 ms 18004 KB Output is correct
12 Correct 27 ms 19668 KB Output is correct
13 Correct 47 ms 27844 KB Output is correct
14 Correct 95 ms 29148 KB Output is correct
15 Correct 131 ms 29476 KB Output is correct
16 Correct 91 ms 25784 KB Output is correct
17 Correct 71 ms 24756 KB Output is correct
18 Correct 29 ms 19768 KB Output is correct
19 Correct 93 ms 29064 KB Output is correct
20 Correct 140 ms 29576 KB Output is correct
21 Correct 87 ms 25968 KB Output is correct
22 Correct 79 ms 24804 KB Output is correct
23 Correct 103 ms 30392 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15700 KB Output is correct
2 Correct 9 ms 15700 KB Output is correct
3 Correct 9 ms 15700 KB Output is correct
4 Correct 8 ms 15556 KB Output is correct
5 Correct 8 ms 15572 KB Output is correct
6 Correct 9 ms 15700 KB Output is correct
7 Correct 7 ms 15572 KB Output is correct
8 Correct 8 ms 15640 KB Output is correct
9 Correct 10 ms 15808 KB Output is correct
10 Correct 8 ms 15572 KB Output is correct
11 Correct 17 ms 18004 KB Output is correct
12 Correct 27 ms 19668 KB Output is correct
13 Correct 47 ms 27844 KB Output is correct
14 Correct 95 ms 29148 KB Output is correct
15 Correct 131 ms 29476 KB Output is correct
16 Correct 91 ms 25784 KB Output is correct
17 Correct 71 ms 24756 KB Output is correct
18 Correct 29 ms 19768 KB Output is correct
19 Correct 93 ms 29064 KB Output is correct
20 Correct 140 ms 29576 KB Output is correct
21 Correct 87 ms 25968 KB Output is correct
22 Correct 79 ms 24804 KB Output is correct
23 Correct 103 ms 30392 KB Output is correct
24 Correct 8 ms 15568 KB Output is correct
25 Correct 113 ms 18036 KB Output is correct
26 Correct 144 ms 19740 KB Output is correct
27 Correct 2251 ms 27944 KB Output is correct
28 Correct 927 ms 29260 KB Output is correct
29 Correct 2506 ms 29528 KB Output is correct
30 Correct 1436 ms 25988 KB Output is correct
31 Correct 1356 ms 24840 KB Output is correct
32 Correct 126 ms 19916 KB Output is correct
33 Correct 987 ms 29168 KB Output is correct
34 Correct 2676 ms 29512 KB Output is correct
35 Correct 1618 ms 26036 KB Output is correct
36 Correct 1397 ms 24904 KB Output is correct
37 Correct 768 ms 30492 KB Output is correct
38 Correct 1956 ms 37404 KB Output is correct