oj.uz

Submission #1040682

# Submission time Handle Problem Language Result Execution time Memory
1040682 2024-08-01T08:27:28 Z ㅇㅇ(#11044) The Ties That Guide Us (CEOI23_incursion) C++17
0 / 100
 73 ms 13312 KB 
#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> G[45009];
int _N, _S[45009], C[45009], V[45009], P[45009];

void dfs(int x, int p) {
    _S[x] = 1;
    int mx = 0;
    for(auto it: G[x]) if(it != p) {
        dfs(it, x);
        _S[x] += _S[it];
        mx = max(mx, _S[it]);
    }
    if(x == p) {
        C[x] = 0;
        return;
    }
    int r = _N - _S[x];
    mx = max(mx, r);
    if(r == mx) C[x] = 1;
    else C[x] = 0;
}

vector<int> mark(vector<pair<int, int>> F, int safe) {
    _N = F.size() + 1;
    for(int i=1; i<=_N; i++) G[i].clear();
    for(auto [u, v]: F) {
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(safe, safe);
    vector<int> ret(_N);
    for(int i=1; i<=_N; i++) ret[i-1] = C[i];
    return ret;
}

void go(int x, int p) {
    P[x] = p;
    _S[x] = 1;
    for(auto it: G[x]) if(it != p) {
        go(it, x);
        _S[x] += _S[it];
    }
}

void fnd(int x, int t) {
    V[x] = 1;
    vector<pair<int, int>> A;
    for(auto it: G[x]) if(it != P[x]) A.push_back({_S[it], it});
    if(x != P[x]) A.push_back({_N - _S[x], P[x]});
    sort(A.begin(), A.end());
    reverse(A.begin(), A.end());
    if(C[x] == 1) {
        int c = 0;
        for(auto [s, it]: A) if(s == A[0].first) ++c;
        if(c == 1) return fnd(A[0].second, visit(A[0].second));
        else {
            for(auto [s, it]: A) if(!V[it] && s == A[0].first) {
                if(visit(it) == 1) visit(x);
                else return fnd(it, 0);
            }
        }
    }
    if(C[x] == 0) {
        for(auto [s, it]: A) if(!V[it] && s < A[0].first) {
            if(visit(it) == 1) visit(x);
            else return fnd(it, 0);
        }
    }
}

void locate(vector<pair<int, int>> F, int curr, int t) {
    _N = F.size() + 1;
    memset(V, 0, sizeof(V));
    for(int i=1; i<=_N; i++) G[i].clear();
    for(auto [u, v]: F) {
        G[u].push_back(v);
        G[v].push_back(u);
    }
    go(curr, curr);
    fnd(curr, t);
    return;
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3084 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 13312 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 8080 KB Correct
2 Incorrect 73 ms 8040 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3084 KB Not correct
2 Halted 0 ms 0 KB -