oj.uz

Submission #872638

# Submission time Handle Problem Language Result Execution time Memory
872638 2023-11-13T13:23:13 Z Foolestboy Logičari (COCI21_logicari) C++14
10 / 110
 129 ms 25864 KB 
#include <bits/stdc++.h>

#define SQR(x)    (1LL * ((x) * (x)))
#define MASK(i)   (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define fi        first
#define se        second
#define pb        push_back
#define all(x)    x.begin(), x.end()
#define rall(x)   x.rbegin(), x.rend()
#define sz(s)     (int)s.size()
#define prev      __prev
#define next      __next
#define left      __left
#define right     __right

#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned int ui;

using namespace std;

const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const ll INFLL = (ll)2e18 + 7LL;
const ld PI = acos(-1);

const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};

template<class BUI, class TRONG>
    bool minimize(BUI &x, const TRONG y){
        if(x > y){
            x = y;
            return true;
        } else return false;
    }
template<class BUI, class TRONG>
    bool maximize(BUI &x, const TRONG y){
        if(x < y){
            x = y;
            return true;
        } else return false;
    }

/* Author : Bui Nguyen Duc Trong, Luong Van Chanh High School for the gifted*/
/* Template is copied by Trong */

                           /** Losing in Provincial Contests **/
                                    /** TRYING HARDER**/
                                   /**      ORZ     **/

/* -----------------[ MAIN CODE GOES HERE ]----------------- */

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e5 + 10;

int n;
vector<int> adj[N];
int c[N];
int specNode, root;
int f[N][2][2][2][2];

void preDfs(int u, int p){
    c[u] = 1;
    for(int v : adj[u]){
        if(v == p) continue;
        if(c[v] == 0) preDfs(v, u);
        else if(c[v] == 1){
            specNode = v;
            root = u;
            return;
        }
    }
    c[u] = 2;
}

int dfs(int u, int p, int me, int up, int rt, int sp){
    if(f[u][me][up][rt][sp] != -1) return f[u][me][up][rt][sp];
    if(u == root && rt != me) return f[u][me][up][rt][sp] = INF;
    if(u == specNode && sp != me) return f[u][me][up][rt][sp] = INF;
    if(u == specNode && rt && up) return f[u][me][up][rt][sp] = INF;
    f[u][me][up][rt][sp] = INF;
    ll tot = 0;
    for(int v : adj[u]){
        if(v == p || (u == specNode && v == root) || (u == root && v == specNode)) continue;
        tot += dfs(v, u, 0, me, rt, sp);
    }
    if(up || (u == specNode && rt)){
        if(tot < INF) f[u][me][up][rt][sp] = tot + me;
    } else{
        for(int v : adj[u]){
            if(v == p || (u == specNode && v == root) || (u == root && v == specNode)) continue;
            ll z = tot - dfs(v, u, 0, me, rt, sp) + dfs(v, u, 1, me, rt, sp);
            if(z < INF) minimize(f[u][me][up][rt][sp], z + me);
        }
    }
    return f[u][me][up][rt][sp];
}

void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 1; i <= n; i++) c[i] = 0;
    preDfs(1, 0);
    int root = 1 != specNode ? 1 : 2;
    int ans = INF;
    memset(f, -1, sizeof f);
    for(int x = 0; x < 2; x++){
        for(int y = 0; y < 2; y++){
            minimize(ans, dfs(root, 0, x, y, x, y));
        }
    }
    cout << (ans < INF ? ans : -1) << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    const bool multitest = 0;
    int tt = 1; if(multitest) cin >> tt;

    while( tt-- ){

        solve();

    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9308 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 2 ms 9308 KB Output is correct
4 Correct 2 ms 9308 KB Output is correct
5 Correct 129 ms 25864 KB Output is correct
6 Correct 120 ms 25860 KB Output is correct
7 Correct 117 ms 25684 KB Output is correct
8 Correct 114 ms 25680 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9308 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Incorrect 2 ms 9308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9308 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Incorrect 2 ms 9308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9308 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 2 ms 9308 KB Output is correct
4 Correct 2 ms 9308 KB Output is correct
5 Correct 129 ms 25864 KB Output is correct
6 Correct 120 ms 25860 KB Output is correct
7 Correct 117 ms 25684 KB Output is correct
8 Correct 114 ms 25680 KB Output is correct
9 Correct 3 ms 9308 KB Output is correct
10 Correct 2 ms 9308 KB Output is correct
11 Incorrect 2 ms 9308 KB Output isn't correct
12 Halted 0 ms 0 KB -