oj.uz

Submission #1070382

# Submission time Handle Problem Language Result Execution time Memory
1070382 2024-08-22T13:47:46 Z GrindMachine The Ties That Guide Us (CEOI23_incursion) C++17
30 / 100
 196 ms 10200 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*

read the edi a long time ago, dont really remember much from there

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "incursion.h"

std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
    // return {2, 2, 0};
    int n = sz(F)+1;
    vector<vector<int>> adj(n+5);
    for(auto [u,v] : F){
        adj[u].pb(v), adj[v].pb(u);
    }

    int r = -1;
    rep1(i,n){
        if(sz(adj[i]) == 2){
            r = i;
        }
    }

    assert(r != -1);
    vector<int> par(n+5);

    auto dfs = [&](int u, int p, auto &&dfs) -> void{
        par[u] = p;
        trav(v,adj[u]){
            if(v == p) conts;
            dfs(v,u,dfs);
        }
    };

    dfs(r,-1,dfs);

    vector<int> ans(n);
    while(safe != -1){
        ans[safe-1] = 1;
        safe = par[safe];
    }

    return ans;
}

void locate(std::vector<std::pair<int, int>> F, int curr, int cnt) {
    int n = sz(F)+1;
    vector<vector<int>> adj(n+5);
    for(auto [u,v] : F){
        adj[u].pb(v), adj[v].pb(u);
    }

    int r = -1;
    rep1(i,n){
        if(sz(adj[i]) == 2){
            r = i;
        }
    }

    assert(r != -1);
    vector<int> par(n+5), subsiz(n+5);

    auto dfs = [&](int u, int p, auto &&dfs) -> void{
        par[u] = p;
        subsiz[u] = 1;
        trav(v,adj[u]){
            if(v == p) conts;
            dfs(v,u,dfs);
            subsiz[u] += subsiz[v];
        }
    };

    dfs(r,-1,dfs);

    while(!cnt){
        cnt = visit(par[curr]);
        curr = par[curr];
    }

    while(true){
        vector<pii> ord;
        trav(v,adj[curr]){
            if(v == par[curr]) conts;
            ord.pb({subsiz[v],v});
        }
        sort(rall(ord));

        int nxt = -1;
        for(auto [s,v] : ord){
            int x = visit(v);
            if(x){
                nxt = v;
                break;
            }
            visit(curr);
        }

        if(nxt == -1) break;
        curr = nxt;
    }

    // int x;
    // x = visit(3);
    // if (x != 2) {
    //     return;
    // }
    // x = visit(1);
    // if (x != 0) {
    //     return;
    // }
    // x = visit(3);
    // if (x != 2) {
    //     return;
    // }
    // x = visit(2);
    // if (x != 2) {
    //     return;
    // }
    // 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 Correct 0 ms 1272 KB Correct

Subtask #1
0.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 7836 KB Correct
2 Correct 72 ms 8064 KB Correct
3 Correct 80 ms 8028 KB Correct
4 Correct 83 ms 8988 KB Correct
5 Correct 162 ms 9036 KB Correct
6 Correct 196 ms 9060 KB Correct
7 Correct 65 ms 7752 KB Correct
8 Correct 68 ms 7688 KB Correct
9 Correct 80 ms 7700 KB Correct
10 Correct 80 ms 7504 KB Correct
11 Correct 77 ms 7512 KB Correct
12 Correct 83 ms 7684 KB Correct
13 Correct 86 ms 7664 KB Correct
14 Correct 62 ms 5876 KB Correct
15 Correct 64 ms 5960 KB Correct
16 Correct 99 ms 7500 KB Correct
17 Correct 87 ms 7648 KB Correct
18 Correct 93 ms 7664 KB Correct
19 Correct 77 ms 7332 KB Correct
20 Correct 73 ms 5972 KB Correct
21 Correct 70 ms 5952 KB Correct
22 Correct 67 ms 5840 KB Correct
23 Correct 66 ms 5952 KB Correct
24 Correct 54 ms 5952 KB Correct
25 Correct 72 ms 5972 KB Correct
26 Correct 70 ms 7664 KB Correct
27 Correct 67 ms 7760 KB Correct
28 Correct 73 ms 7760 KB Correct
29 Correct 87 ms 7780 KB Correct
30 Correct 83 ms 8032 KB Correct
31 Correct 93 ms 7516 KB Correct
32 Correct 93 ms 7760 KB Correct
33 Correct 69 ms 7504 KB Correct
34 Correct 75 ms 7836 KB Correct
35 Correct 70 ms 7524 KB Correct
36 Correct 76 ms 7860 KB Correct
37 Correct 80 ms 7520 KB Correct
38 Correct 76 ms 7580 KB Correct
39 Correct 78 ms 7836 KB Correct
40 Correct 83 ms 7500 KB Correct
41 Correct 88 ms 7752 KB Correct
42 Correct 91 ms 7504 KB Correct
43 Correct 80 ms 7680 KB Correct
44 Correct 75 ms 7904 KB Correct
45 Correct 81 ms 7572 KB Correct
46 Correct 86 ms 7836 KB Correct
47 Correct 71 ms 7840 KB Correct
48 Correct 81 ms 7688 KB Correct
49 Correct 78 ms 7752 KB Correct
50 Correct 80 ms 7580 KB Correct
51 Correct 87 ms 7504 KB Correct
52 Correct 69 ms 7684 KB Correct
53 Correct 84 ms 7652 KB Correct
54 Correct 79 ms 7760 KB Correct
55 Correct 82 ms 7324 KB Correct
56 Correct 79 ms 7760 KB Correct
57 Correct 84 ms 7592 KB Correct
58 Correct 82 ms 7672 KB Correct
59 Correct 99 ms 7584 KB Correct
60 Correct 87 ms 7580 KB Correct
61 Correct 81 ms 7612 KB Correct
62 Correct 82 ms 7688 KB Correct
63 Correct 82 ms 7556 KB Correct
64 Correct 82 ms 7492 KB Correct
65 Correct 79 ms 7492 KB Correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1272 KB Correct
2 Incorrect 170 ms 10200 KB Not correct
3 Halted 0 ms 0 KB -