oj.uz

Submission #933378

# Submission time Handle Problem Language Result Execution time Memory
933378 2024-02-25T15:14:04 Z themm1 Inside information (BOI21_servers) C++17
5 / 100
 3500 ms 11240 KB 
#include <bits/stdc++.h>
using namespace std;

template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &pr) {out << "(" << pr.first << "; " << pr.second << ")";return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &s) {out << "{";for(const auto &x : s)out << x << ", ";out << "}";return out;}
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &m) {out << "{";for(const auto &x : m)out << x << ", ";out << "}";return out;}
template<class T>
ostream& operator<<(ostream& out, const vector<T> &a){out << "[";for(const auto &x : a)out << x << ", ";out << "]";return out;}

#define dmp(x) cerr << #x << " = " << x << endl
#define dmpn(x) cerr << #x << " = " << x << "; "

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define contains(s,x) ((s).find(x) != (s).end())
const int MOD = 998244353;

struct Edge {
        int u, id;
};

int N, K;
vector<vector<Edge>> adj;

int dfs(int u, int p, int prev_id, int target) {
        int cnt = (target == -1 || u == target);
        for (Edge e : adj[u]) {
                if (e.u != p && e.id > prev_id) {
                        cnt += dfs(e.u, u, e.id, target);
                }
        }
        return cnt;
}

void solve() {
        cin >> N >> K;
        adj.assign(N, {});

        int Q = N - 1 + K, edge_idx = 1;
        while (Q--) {
                char type;
                int u;
                cin >> type >> u;
                u--;
                if (type == 'S') {
                        int v;
                        cin >> v;
                        v--;

                        adj[u].pb({ v, edge_idx });
                        adj[v].pb({ u, edge_idx });
                        edge_idx++;
                } else if (type == 'Q') {
                        int v;
                        cin >> v;
                        v--;

                        int cnt = dfs(v, -1, 0, u);
                        if (cnt > 0) cout << "yes" << endl;
                        else cout << "no" << endl;
                } else {
                        int cnt = dfs(u, -1, 0, -1);
                        cout << cnt << endl;
                }
        }
}

int32_t main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);

        int t = 1;
        // cin >> t;
        while (t--) {
                solve();
        }
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 147 ms 1364 KB Output is correct
2 Correct 164 ms 2176 KB Output is correct
3 Correct 228 ms 2316 KB Output is correct
4 Correct 173 ms 2388 KB Output is correct
5 Correct 188 ms 2368 KB Output is correct
6 Correct 1195 ms 2284 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 147 ms 1364 KB Output is correct
2 Correct 164 ms 2176 KB Output is correct
3 Correct 228 ms 2316 KB Output is correct
4 Correct 173 ms 2388 KB Output is correct
5 Correct 188 ms 2368 KB Output is correct
6 Correct 1195 ms 2284 KB Output is correct
7 Correct 148 ms 1648 KB Output is correct
8 Correct 162 ms 1940 KB Output is correct
9 Correct 308 ms 2128 KB Output is correct
10 Correct 152 ms 2080 KB Output is correct
11 Correct 155 ms 1876 KB Output is correct
12 Correct 1267 ms 2696 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 153 ms 1380 KB Output is correct
2 Execution timed out 3565 ms 6644 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 153 ms 1380 KB Output is correct
2 Execution timed out 3565 ms 6644 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 1360 KB Output is correct
2 Correct 189 ms 10604 KB Output is correct
3 Correct 201 ms 10580 KB Output is correct
4 Execution timed out 3503 ms 9768 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 1360 KB Output is correct
2 Correct 189 ms 10604 KB Output is correct
3 Correct 201 ms 10580 KB Output is correct
4 Execution timed out 3503 ms 9768 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 1616 KB Output is correct
2 Execution timed out 3563 ms 11240 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 1616 KB Output is correct
2 Execution timed out 3563 ms 11240 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 155 ms 1360 KB Output is correct
2 Correct 188 ms 10580 KB Output is correct
3 Correct 198 ms 10580 KB Output is correct
4 Execution timed out 3544 ms 9840 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 155 ms 1360 KB Output is correct
2 Correct 188 ms 10580 KB Output is correct
3 Correct 198 ms 10580 KB Output is correct
4 Execution timed out 3544 ms 9840 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 156 ms 1512 KB Output is correct
2 Correct 161 ms 2716 KB Output is correct
3 Correct 223 ms 2552 KB Output is correct
4 Correct 152 ms 2384 KB Output is correct
5 Correct 158 ms 2356 KB Output is correct
6 Correct 1185 ms 2624 KB Output is correct
7 Correct 152 ms 1692 KB Output is correct
8 Execution timed out 3546 ms 6596 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 156 ms 1512 KB Output is correct
2 Correct 161 ms 2716 KB Output is correct
3 Correct 223 ms 2552 KB Output is correct
4 Correct 152 ms 2384 KB Output is correct
5 Correct 158 ms 2356 KB Output is correct
6 Correct 1185 ms 2624 KB Output is correct
7 Correct 152 ms 1692 KB Output is correct
8 Execution timed out 3546 ms 6596 KB Time limit exceeded
9 Halted 0 ms 0 KB -