oj.uz

Submission #755498

# Submission time Handle Problem Language Result Execution time Memory
755498 2023-06-10T07:49:45 Z RecursiveCo Wells (CEOI21_wells) C++14
0 / 100
 3 ms 768 KB 
// CF template, version 3.0

#include <bits/stdc++.h>

using namespace std;

#define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0)
#define getTest int t; cin >> t
#define eachTest for (int _var=0;_var<t;_var++)
#define get(name) int (name); cin >> (name)
#define out(o) cout << (o)
#define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
#define sortl(name) sort((name).begin(), (name).end())
#define rev(name) reverse((name).begin(), (name).end())
#define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
#define decision(b) if (b){out("YES");}else{out("NO");}

#define int long long int

vector<int> parent;

int find(int v) {
    if (v == parent[v]) return v;
    else return parent[v] = find(parent[v]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    parent[a] = b;
}

signed main() {
    improvePerformance;
    get(n);
    get(k);
    vector<vector<int>> adjList(n);
    forto(n - 1, i) {
        get(a);
        get(b);
        a--;
        b--;
        adjList[a].push_back(b);
        adjList[b].push_back(a);
    }
    vector<int> height(n);
    vector<int> inordindex(n, 1e18);
    vector<int> inordheight;
    vector<int> inordnode;
    vector<bool> visited(n, false);
    stack<int> seen;
    int v = 0;
    int h = 0;
    int c = 0;
    seen.push(0);
    while (!seen.empty()) {
        height[v] = h;
        visited[v] = true;
        inordheight.push_back(h);
        inordnode.push_back(v);
        inordindex[v] = min(inordindex[v], c++);
        bool found = false;
        for (int con: adjList[v]) {
            if (!visited[con]) {
                found = true;
                seen.push(con);
                v = con;
                h++;
                break;
            }
        }
        if (!found) {
            seen.pop();
            if (!seen.empty()) v = seen.top();
            h--;
        }
    }
    int m = inordheight.size();
    vector<vector<int>> RMQ(m, vector<int>(25));
    for (int i = m - 1; i >= 0; i--) {
        RMQ[i][0] = inordheight[i];
        int p = 1;
        for (int j = 1; j < 25; j++) {
            p *= 2;
            if (i + p >= m) break;
            RMQ[i][j] = min(RMQ[i][j - 1], RMQ[i + p / 2][j - 1]);
        }
    }
    vector<int> lg;
    int p = 1;
    int l = -1;
    forto(m, i) {
        if (i == 0) lg.push_back(-1);
        else if (i == p) {
            lg.push_back(++l);
            p *= 2;
        } else lg.push_back(l);
    }

    vector<int> nodes;
    forto(n, i) parent.push_back(i);

    vector<vector<int>> distances(n, vector<int>(n, 0));

    forto(n, i) {
        int maxd = 0;
        forto(n, j) {
            if (j == i) continue;
            int hi = height[i];
            int hj = height[j];
            int ii = inordindex[i];
            int ij = inordindex[j];
            if (ii > ij) {
                swap(hi, hj);
                swap(ii, ij);
            }
            int len = ij - ii + 1;
            int loga = lg[len];
            int left = RMQ[ii][loga];
            int right = RMQ[ij - (1 << loga) + 1][loga];
            int hlca = min(left, right);
            int dist = hi - hlca + hj - hlca;
            maxd = max(maxd, dist);
            if (dist == k) unite(i, j);
            distances[i][j] = dist;
        }
    }

    bool can = false;
    vector<vector<int>> dsucoms(n);

    forto(n, i) {
        dsucoms[find(i)].push_back(i);
    }

    forto(n, i) {
        if (dsucoms[i].size()) {
            bool found = false;
            for (int n1: dsucoms[i]) {
                for (int n2: dsucoms[i]) {
                    if (n1 == n2) continue;
                    if (distances[n1][n2] <= k - 1) {
                        found = true;
                        break;
                    }
                }
                if (found) break;
            }
            if (!found) {
                bool all = true;
                forto(n, x) {
                    forto(n, y) {
                        bool done = false;
                        for (int node: dsucoms[i]) {
                            if (distances[x][node] + distances[node][y] == distances[x][y] && distances[x][y] == k - 1) {
                                done = true;
                                break;
                            }
                        }
                        if (!done && distances[x][y] == k - 1) {
                            all = false;
                            break;
                        }
                    }
                    if (!all) break;
                }
                if (all) {
                    can = true;
                    break;
                }
            }
        }
    }

    decision(can);
    out("\n");
    out(0);
}

Compilation message

wells.cpp: In function 'int main()':
wells.cpp:10:23: warning: unnecessary parentheses in declaration of 'n' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
wells.cpp:36:5: note: in expansion of macro 'get'
   36 |     get(n);
      |     ^~~
wells.cpp:10:23: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
wells.cpp:37:5: note: in expansion of macro 'get'
   37 |     get(k);
      |     ^~~
wells.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
wells.cpp:39:5: note: in expansion of macro 'forto'
   39 |     forto(n - 1, i) {
      |     ^~~~~
wells.cpp:10:23: warning: unnecessary parentheses in declaration of 'a' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
wells.cpp:40:9: note: in expansion of macro 'get'
   40 |         get(a);
      |         ^~~
wells.cpp:10:23: warning: unnecessary parentheses in declaration of 'b' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
wells.cpp:41:9: note: in expansion of macro 'get'
   41 |         get(b);
      |         ^~~
wells.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
wells.cpp:93:5: note: in expansion of macro 'forto'
   93 |     forto(m, i) {
      |     ^~~~~
wells.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
wells.cpp:102:5: note: in expansion of macro 'forto'
  102 |     forto(n, i) parent.push_back(i);
      |     ^~~~~
wells.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
wells.cpp:106:5: note: in expansion of macro 'forto'
  106 |     forto(n, i) {
      |     ^~~~~
wells.cpp:15:35: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
wells.cpp:108:9: note: in expansion of macro 'forto'
  108 |         forto(n, j) {
      |         ^~~~~
wells.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
wells.cpp:133:5: note: in expansion of macro 'forto'
  133 |     forto(n, i) {
      |     ^~~~~
wells.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
wells.cpp:137:5: note: in expansion of macro 'forto'
  137 |     forto(n, i) {
      |     ^~~~~
wells.cpp:15:35: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
wells.cpp:152:17: note: in expansion of macro 'forto'
  152 |                 forto(n, x) {
      |                 ^~~~~
wells.cpp:15:35: warning: unnecessary parentheses in declaration of 'y' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
wells.cpp:153:21: note: in expansion of macro 'forto'
  153 |                     forto(n, y) {
      |                     ^~~~~

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Partially correct 3 ms 768 KB Output is partially correct
3 Partially correct 1 ms 724 KB Output is partially correct
4 Partially correct 2 ms 700 KB Output is partially correct
5 Partially correct 2 ms 724 KB Output is partially correct
6 Partially correct 2 ms 724 KB Output is partially correct
7 Correct 1 ms 724 KB Output is correct
8 Partially correct 2 ms 724 KB Output is partially correct
9 Partially correct 3 ms 724 KB Output is partially correct
10 Correct 2 ms 684 KB Output is correct
11 Incorrect 1 ms 724 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Partially correct 3 ms 768 KB Output is partially correct
3 Partially correct 1 ms 724 KB Output is partially correct
4 Partially correct 2 ms 700 KB Output is partially correct
5 Partially correct 2 ms 724 KB Output is partially correct
6 Partially correct 2 ms 724 KB Output is partially correct
7 Correct 1 ms 724 KB Output is correct
8 Partially correct 2 ms 724 KB Output is partially correct
9 Partially correct 3 ms 724 KB Output is partially correct
10 Correct 2 ms 684 KB Output is correct
11 Incorrect 1 ms 724 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Partially correct 3 ms 768 KB Output is partially correct
3 Partially correct 1 ms 724 KB Output is partially correct
4 Partially correct 2 ms 700 KB Output is partially correct
5 Partially correct 2 ms 724 KB Output is partially correct
6 Partially correct 2 ms 724 KB Output is partially correct
7 Correct 1 ms 724 KB Output is correct
8 Partially correct 2 ms 724 KB Output is partially correct
9 Partially correct 3 ms 724 KB Output is partially correct
10 Correct 2 ms 684 KB Output is correct
11 Incorrect 1 ms 724 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Partially correct 3 ms 768 KB Output is partially correct
3 Partially correct 1 ms 724 KB Output is partially correct
4 Partially correct 2 ms 700 KB Output is partially correct
5 Partially correct 2 ms 724 KB Output is partially correct
6 Partially correct 2 ms 724 KB Output is partially correct
7 Correct 1 ms 724 KB Output is correct
8 Partially correct 2 ms 724 KB Output is partially correct
9 Partially correct 3 ms 724 KB Output is partially correct
10 Correct 2 ms 684 KB Output is correct
11 Incorrect 1 ms 724 KB Output isn't correct
12 Halted 0 ms 0 KB -