oj.uz

답안 #1072199

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1072199 2024-08-23T15:31:41 Z Wael The Ties That Guide Us (CEOI23_incursion) C++17
0 / 100
 89 ms 14944 KB 
#include <bits/stdc++.h>
#include "incursion.h"
//#include "sample_grader.cpp"
using namespace std;

vector<int> mark(vector<pair<int, int>> F, int safe) {
    --safe;
    int n = F.size() + 1;
    vector<vector<int>> adj(n);
    for (auto [u, v] : F) {
        --u, --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> sz(n, 1), t(n);
    function<void(int, int)> dfs = [&](int u, int p) {
        for (auto v : adj[u]) {
            if (v == p) {
                continue;
            }
            dfs(v, u);
            sz[u] += sz[v];
        }
        if (u != safe && n - sz[u] >= sz[u]) {
            t[u] = 1;
        }
    };
    dfs(safe, -1);

    return t;
}

void locate(vector<pair<int, int>> F, int curr, int t) {
    --curr;
    int n = F.size() + 1;
    vector<vector<int>> adj(n);
    for (auto [u, v] : F) {
        --u, --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> sz(n, 1), par(n, -1);
    function<void(int, int)> calc = [&](int u, int p) {
        for (auto v : adj[u]) {
            if (v == p) {
                continue;
            }
            calc(v, u);
            sz[u] += sz[v];
        }

        if (n - sz[u] == sz[u]) {
            par[u] = p;
            par[p] = u;
        } else if (n - sz[u] > sz[u]) {
            par[u] = p;
        }
    };
    calc(0, -1);

    fill(sz.begin(), sz.end(), 1);
    for (int i = 0; i < n; ++i) {
        if (par[i] == -1) {
            calc(i, -1);
        }
        if (par[par[i]] == i) {
            calc(i, -1);
            sz[par[i]] = n;
            break;
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < adj[i].size(); ++j) {
            int v = adj[i][j];
            if (v == par[i]) {
                swap(adj[i][j], adj[i].back());
                adj[i].pop_back();
                break;
            }
        }
        sort(adj[i].begin(), adj[i].end(), [&](int u, int v) {
            return sz[u] > sz[v];
        });
    }

    vector<int> cnt(n);
    function<void(int)> dfs = [&](int u) {
        ++cnt[u];
        if (t == 1) {
            t = visit(par[u] + 1);
            dfs(par[u]);
        } else {
            if (adj[u].size() < cnt[u]) {
                return;
            }
            t = visit(adj[u][cnt[u] - 1] + 1);
            dfs(adj[u][cnt[u] - 1]);
        }
    };
    dfs(curr);
}

Compilation message

incursion.cpp: In function 'void locate(std::vector<std::pair<int, int> >, int, int)':
incursion.cpp:76:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (int j = 0; j < adj[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~
incursion.cpp: In lambda function:
incursion.cpp:96:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   96 |             if (adj[u].size() < cnt[u]) {
interface.cpp: In function 'int main()':
interface.cpp:44:55: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     if(fread(T.data(), sizeof(int), 2 * N - 2, stdin) != 2 * N - 2) exit(0);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
interface.cpp:50:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         int l = (numbers.size() == N ? N : 0);
      |                  ~~~~~~~~~~~~~~~^~~~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 768 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 84 ms 14944 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 8028 KB Correct
2 Incorrect 77 ms 8096 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 768 KB Not correct
2 Halted 0 ms 0 KB -