oj.uz

Submission #798379

# Submission time Handle Problem Language Result Execution time Memory
798379 2023-07-30T16:21:10 Z PixelCat Simurgh (IOI17_simurgh) C++14
30 / 100
 197 ms 3672 KB 
#include "simurgh.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 500;

vector<pii> adj[MAXN + 10];  // { node, edge id }

struct Tree {
    set<int> edge;
    set<int> suseid;
    int par[MAXN + 10];
    int dep[MAXN + 10];
    int peid[MAXN + 10];
    bool good[MAXN + 10];
    bool sussy[MAXN + 10];
    vector<int> get_edges() {
        vector<int> ids;
        for(auto &i:edge) ids.eb(i);
        return ids;
    }
    int query() {
        // cerr << "query: ";
        // out();
        return count_common_roads(get_edges());
    }
    void dfs(int x, int p, int d, int pe, bool tree_edge_only = true) {
        if(p < 0) {
            memset(dep, 0, sizeof(dep));
        }
        par[x] = p;
        dep[x] = d;
        peid[x] = pe;
        good[x] = !suseid.count(pe);
        sussy[x] = !good[x];
        for(auto &i:adj[x]) if(i.F != p && dep[i.F] == 0) {
            if(tree_edge_only && !edge.count(i.S)) continue;
            else if(!tree_edge_only) {
                edge.insert(i.S);
                suseid.insert(i.S);
            }
            dfs(i.F, x, d + 1, i.S, tree_edge_only);
            good[x] = good[x] && good[i.F];
            sussy[x] = sussy[x] && good[i.F];
        }
    }
    void collect(int x, int p, set<int> &subtree) {
        subtree.insert(x);
        for(auto &i:adj[x]) if(i.F != p && edge.count(i.S)) {
            collect(i.F, x, subtree);
        }
    }
    void build_tree(int N) {
        For(_, 1, N - 1) {
            dfs(0, -1, 1, -1);
            // For(i, 0, N - 1) cerr << par[i] << " \n"[i == N - 1];
            // For(i, 0, N - 1) cerr << peid[i] << " \n"[i == N - 1];

            int x = -1;
            For(i, 0, N - 1) if(sussy[i]) x = i;
            assert(x >= 0);
            suseid.erase(peid[x]);
            
            int cnt = query();
            edge.erase(peid[x]);

            set<int> subtree;
            collect(x, par[x], subtree);
            
            for(auto &a:subtree) for(auto &e:adj[a]) {
                if(subtree.count(e.F)) continue;
                edge.insert(e.S);
                if(query() > cnt) goto FOUND;
                edge.erase(e.S);
            }
            edge.insert(peid[x]);
            FOUND:;
            out();
        }
    }
    void out() {
        #ifdef NYAOWO
        cerr << "tree: ";
        for(auto &i:get_edges()) {
            cerr << i << " ";
        }
        cerr << "\n";
        #endif
    }
} tr;

vector<int> find_roads(int N, vector<int> U, vector<int> V) {
    int M = sz(U);
    For(i, 0, M - 1) {
        adj[U[i]].eb(V[i], i);
        adj[V[i]].eb(U[i], i);
    }
    tr.dfs(0, -1, 1, -1, false);
    tr.build_tree(N);
    return tr.get_edges();

    // vector<int> r(n - 1);
    // for(int i = 0; i < n - 1; i++)
    //     r[i] = i;
    // int common = count_common_roads(r);
    // if(common == n - 1)
    //     return r;
    // r[0] = n - 1;
    // return r;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 0 ms 212 KB correct
5 Correct 1 ms 312 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 1 ms 320 KB correct
13 Correct 1 ms 212 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 0 ms 212 KB correct
5 Correct 1 ms 312 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 1 ms 320 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 5 ms 376 KB correct
15 Correct 3 ms 340 KB correct
16 Correct 4 ms 340 KB correct
17 Correct 4 ms 320 KB correct
18 Correct 2 ms 340 KB correct
19 Correct 4 ms 340 KB correct
20 Correct 3 ms 320 KB correct
21 Correct 5 ms 340 KB correct
22 Correct 6 ms 340 KB correct
23 Correct 3 ms 316 KB correct
24 Correct 4 ms 320 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 4 ms 320 KB correct
27 Correct 4 ms 340 KB correct
28 Correct 2 ms 340 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 4 ms 340 KB correct
31 Correct 5 ms 340 KB correct
32 Correct 5 ms 340 KB correct
33 Correct 4 ms 340 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 0 ms 212 KB correct
5 Correct 1 ms 312 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 1 ms 320 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 5 ms 376 KB correct
15 Correct 3 ms 340 KB correct
16 Correct 4 ms 340 KB correct
17 Correct 4 ms 320 KB correct
18 Correct 2 ms 340 KB correct
19 Correct 4 ms 340 KB correct
20 Correct 3 ms 320 KB correct
21 Correct 5 ms 340 KB correct
22 Correct 6 ms 340 KB correct
23 Correct 3 ms 316 KB correct
24 Correct 4 ms 320 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 4 ms 320 KB correct
27 Correct 4 ms 340 KB correct
28 Correct 2 ms 340 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 4 ms 340 KB correct
31 Correct 5 ms 340 KB correct
32 Correct 5 ms 340 KB correct
33 Correct 4 ms 340 KB correct
34 Incorrect 197 ms 1544 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Incorrect 116 ms 3672 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 0 ms 212 KB correct
5 Correct 1 ms 312 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 1 ms 320 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 5 ms 376 KB correct
15 Correct 3 ms 340 KB correct
16 Correct 4 ms 340 KB correct
17 Correct 4 ms 320 KB correct
18 Correct 2 ms 340 KB correct
19 Correct 4 ms 340 KB correct
20 Correct 3 ms 320 KB correct
21 Correct 5 ms 340 KB correct
22 Correct 6 ms 340 KB correct
23 Correct 3 ms 316 KB correct
24 Correct 4 ms 320 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 4 ms 320 KB correct
27 Correct 4 ms 340 KB correct
28 Correct 2 ms 340 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 4 ms 340 KB correct
31 Correct 5 ms 340 KB correct
32 Correct 5 ms 340 KB correct
33 Correct 4 ms 340 KB correct
34 Incorrect 197 ms 1544 KB WA in grader: NO
35 Halted 0 ms 0 KB -