oj.uz

Submission #1040576

# Submission time Handle Problem Language Result Execution time Memory
1040576 2024-08-01T07:35:58 Z ㅇㅇ(#11044) The Ties That Guide Us (CEOI23_incursion) C++17
0 / 100
 86 ms 17252 KB 
#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;

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

void dfs(int x, int p) {
    _S[x] = 1;
    set<int> A;
    for(auto it: G[x]) if(it != p) {
        dfs(it, x);
        _S[x] += _S[it];
        A.insert(_S[it]);
    }
    if(x == p) {
        C[x] = 0;
        return;
    }
    int r = _N - _S[x];
    A.insert(r);
    int c = 0;
    for(auto it: A) if(it < r) ++c;
    if(A.size() == c+1) C[x] = 1;
    else C[x] = 0;
}

vector<int> mark(vector<pair<int, int>> F, int safe) {
    _N = F.size() + 1;
    rt = safe;
    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) {
    _S[x] = 1;
    for(auto it: G[x]) if(it != p) {
        go(it, x);
        _S[x] += _S[it];
    }
}

void fnd(int x, int p, int t) {
    V[x] = 1;
    set<int> B;
    vector<pair<int, int>> A;
    for(auto it: G[x]) if(it != p) A.push_back({_S[it], it});
    if(x != p) A.push_back({_N - _S[x], p});
    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) fnd(A[0].second, x, visit(A[0].second));
        else {
            for(auto [s, it]: A) if(!V[it] && s == A[0].first) {
                if(visit(it) == 1) visit(x);
                else {
                    fnd(it, x, 0);
                    break;
                }
            }
        }
    }
    if(C[x] == 0) {
        for(auto [s, it]: A) if(!V[it] && s < A[0].first) {
            if(visit(it) == 1) visit(x);
            else {
                fnd(it, x, 0);
                break;
            }
        }
    }
}

void locate(vector<pair<int, int>> F, int curr, int t) {
    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, curr, t);
    return;
}

Compilation message

incursion.cpp: In function 'void dfs(int, int)':
incursion.cpp:24:17: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |     if(A.size() == c+1) C[x] = 1;
      |        ~~~~~~~~~^~~~~~
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 2 ms 2816 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 30.0

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

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 7800 KB Correct
2 Incorrect 69 ms 7804 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

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