oj.uz

Submission #527336

# Submission time Handle Problem Language Result Execution time Memory
527336 2022-02-17T08:31:22 Z andrei_c1 Speedrun (RMI21_speedrun) C++14
48 / 100
 205 ms 800 KB 
#include <bits/stdc++.h>
#include "speedrun.h"
//#define EVAL

using namespace std;

void assignHints(int subtask, int N, int A[], int B[]) {
    int freq[1001] = {0};

    for(int i = 1; i < N; i++) {
        freq[A[i]]++;
        freq[B[i]]++;
    }

    int center = -1;
    bool is_star = 0;

    for(int i = 1; i <= N && !is_star; i++) {
        if(freq[i] == N - 1) {
            is_star = 1;
            center = i;
        }
    }

    bool grad2 = 1;

    for(int i = 1; i <= N && grad2; i++) {
        if(freq[i] > 2) {
            grad2 = 0;
        }
    }

    if(is_star) { //Arbore stea
        setHintLen(12);
        for(int i = 1; i < N; i++) {
            //hint A[i] => B[i](2)
            //hint B[i] => A[i](2)

            for(int j = 1; j <= 10; j++) {
                if(B[i] & (1 << (j - 1))) {
                    setHint(A[i], j, 1);
                }
            }

            for(int j = 1; j <= 10; j++) {
                if(A[i] & (1 << (j - 1))) {
                    setHint(B[i], j, 1);
                }
            }
        }
        setHint(center, 11, 1);
    } else if(grad2) { //Arbore grad2
        vector<int> edges[1001];
        for(int i = 1; i < N; i++) {
            edges[A[i]].push_back(B[i]);
            edges[B[i]].push_back(A[i]);
        }

        setHintLen(20);

        for(int i = 1; i < N; i++) {
            //hint A[i] => vecinii A[i](2)
            //hint B[i] => vecinii B[i](2)

            int add;

            add = 0;
            for(int node: edges[A[i]]) {
                for(int j = 1; j <= 10; j++) {
                    if(node & (1 << (j - 1))) {
                        setHint(A[i], j + add, 1);
                    }
                }
                add += 10;
            }

            add = 0;
            for(int node: edges[B[i]]) {
                for(int j = 1; j <= 10; j++) {
                    if(node & (1 << (j - 1))) {
                        setHint(B[i], j + add, 1);
                    }
                }
                add += 10;
            }

        }
    } else { //Arbore normal
        setHintLen(N);

        for(int i = 1; i < N; i++) {
            setHint(A[i], B[i], 1);
            setHint(B[i], A[i], 1);
        }
    }
}

int len;
vector<int> parent;
vector<bool> visited;

/*
Arbore normal
7
1 2
1 3
2 4
2 5
5 6
3 7
1
Arbore stea
7
1 2
1 3
1 4
1 5
1 6
1 7
1
Arbore grad2
7
1 2
1 3
2 4
4 6
6 7
3 5
1

3
1 2
1 3
1
*/

void dfs(int start) {
    visited[start] = 1;

    for(int node = 1; node <= len; node++) {
        if(getHint(node) && !visited[node]) {
            parent[node] = start;
            goTo(node);
            dfs(node);
        }
    }
    if(parent[start] != 0) {
        goTo(parent[start]);
    }
}

void dfs_star(int start, int N) {
    visited[start] = 1;

    int node = 0;

    if(getHint(11)) {
        for(int node = 1; node <= N; node++) {
            if(!visited[node]) {
                parent[node] = start;
                goTo(node);
                dfs_star(node, N);
            }
        }
    } else {
        for(int i = 1; i <= 10; i++) {
            if(getHint(i)) {
                node += (1 << (i - 1));
            }
        }

        if(!visited[node]) {
            parent[node] = start;
            goTo(node);
            dfs_star(node, N);
        }
    }

    if(parent[start] != 0) {
        goTo(parent[start]);
    }
}

void dfs_grad2(int start) {
    visited[start] = 1;

    int add = 0, node[2];

    for(int rep = 0; rep < 2; rep++) {
        node[rep] = 0;
        for(int i = 1; i <= 10; i++) {
            if(getHint(i + add)) {
                node[rep] += (1 << (i - 1));
            }
        }
        add += 10;
    }

    for(int rep = 0; rep < 2; rep++) {
        if(!visited[node[rep]] && node[rep]) {
            parent[node[rep]] = start;
            goTo(node[rep]);
            dfs_grad2(node[rep]);
        }
    }

    if(parent[start] != 0) {
        goTo(parent[start]);
    }
}

void speedrun(int subtask, int N, int start) {
    len = getLength();
    visited = vector<bool>(N + 1, 0);
    parent = vector<int>(N + 1, 0);

    if(len == 12) { //Arbore stea
        dfs_star(start, N);
    } else if(len == 20) { //Arbore grad2
        dfs_grad2(start);
    }else if(len == N) { //Arbore normal
        dfs(start);
    }
}

#ifndef EVAL

static map<int, map<int, bool>> mp;
static int length = -1;
static int queries = 0;
static bool length_set = false;
static int current_node = 0;
static set<int> viz;
static map<int, set<int>> neighbours;

void setHintLen(int l) {
    if (length_set) {
        cerr << "Cannot call setHintLen twice" << endl;
        exit(0);
    }
    length = l;
    length_set = true;
}

void setHint(int i, int j, bool b) {
    if (!length_set) {
        cerr << "Must call setHintLen before setHint" << endl;
        exit(0);
    }
    mp[i][j] = b;
}

int getLength() { return length; }

bool getHint(int j) { return mp[current_node][j]; }

bool goTo(int x) {
    if (neighbours[current_node].find(x) == end(neighbours[current_node])) {
        ++queries;
        return false;
    } else {
        viz.insert(current_node = x);
        return true;
    }
}

int main() {
    int N;
    cin >> N;

    int a[N], b[N];
    for (int i = 1; i < N; ++i) {
        cin >> a[i] >> b[i];
        neighbours[a[i]].insert(b[i]);
        neighbours[b[i]].insert(a[i]);
    }

    assignHints(1, N, a, b);

    if (!length_set) {
        cerr << "Must call setHintLen at least once" << endl;
        exit(0);
    }

    cin >> current_node;
    viz.insert(current_node);

    speedrun(1, N, current_node);

    if (viz.size() < N) {
        cerr << "Haven't seen all nodes" << endl;
        exit(0);
    }

    cerr << "OK; " << queries << " incorrect goto's" << endl;
    return 0;
}
#endif

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 700 KB Output is correct
2 Correct 41 ms 780 KB Output is correct
3 Correct 41 ms 784 KB Output is correct
4 Correct 41 ms 800 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 672 KB Output is correct
2 Correct 83 ms 676 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 660 KB Output is correct
2 Correct 205 ms 660 KB Output is correct
3 Correct 120 ms 696 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 328 KB The length is too large
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB The length is too large
2 Halted 0 ms 0 KB -