oj.uz

Submission #733627

# Submission time Handle Problem Language Result Execution time Memory
733627 2023-05-01T05:35:20 Z n0sk1ll Cats or Dogs (JOI18_catdog) C++17
38 / 100
 3000 ms 8116 KB 
#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

#include "catdog.h"

int n;
int kolko=0; //kolko ukupno ukljucenih; ako nije niko ukljucen treba vratiti 0...

graph g(100005);
li dp[100005][3]; //closed, open cat, open dog
int ko[100005]; //0 = niko, 1 = cat, 2 = dog

void dfs(int p, int q)
{
    dp[p][1]=0,dp[p][2]=0;
    for (auto it : g[p]) if (it!=q)
    {
        dfs(it,p);
        dp[p][1]+=min(dp[it][0],dp[it][1]);
        dp[p][2]+=min(dp[it][0],dp[it][2]);
    }

    if (ko[p]==1) dp[p][2]=mod;
    if (ko[p]==2) dp[p][1]=mod;
    dp[p][0]=min(dp[p][1],dp[p][2])+1;
}

int solve()
{
    dfs(1,0);
    return dp[1][0]-1;
}

void initialize(int N, vector<int> A, vector<int> B)
{
    n=N;

    ff(i,0,n-1) g[A[i]].pb(B[i]),g[B[i]].pb(A[i]);
}

int cat(int v)
{
    kolko++,ko[v]=1;
    return solve();
}

int dog(int v)
{
    kolko++,ko[v]=2;
    return solve();
}

int neighbor(int v)
{
    kolko--,ko[v]=0;
    return solve();
}

/*

6
1 2
1 3
1 4
4 5
4 6
8
1 5
2 6
2 3
1 2
8 2
8 3
8 6
8 5

*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2676 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2672 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2672 KB Output is correct
10 Correct 2 ms 2676 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2676 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2676 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2672 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2672 KB Output is correct
10 Correct 2 ms 2676 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2676 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 10 ms 2680 KB Output is correct
18 Correct 13 ms 2736 KB Output is correct
19 Correct 7 ms 2644 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 3 ms 2680 KB Output is correct
22 Correct 3 ms 2684 KB Output is correct
23 Correct 14 ms 2756 KB Output is correct
24 Correct 12 ms 2764 KB Output is correct
25 Correct 6 ms 2644 KB Output is correct
26 Correct 4 ms 2644 KB Output is correct
27 Correct 3 ms 2644 KB Output is correct
28 Correct 5 ms 2772 KB Output is correct
29 Correct 18 ms 2808 KB Output is correct
30 Correct 4 ms 2644 KB Output is correct
31 Correct 2 ms 2644 KB Output is correct
32 Correct 4 ms 2644 KB Output is correct

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2676 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2672 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2672 KB Output is correct
10 Correct 2 ms 2676 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2676 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 10 ms 2680 KB Output is correct
18 Correct 13 ms 2736 KB Output is correct
19 Correct 7 ms 2644 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 3 ms 2680 KB Output is correct
22 Correct 3 ms 2684 KB Output is correct
23 Correct 14 ms 2756 KB Output is correct
24 Correct 12 ms 2764 KB Output is correct
25 Correct 6 ms 2644 KB Output is correct
26 Correct 4 ms 2644 KB Output is correct
27 Correct 3 ms 2644 KB Output is correct
28 Correct 5 ms 2772 KB Output is correct
29 Correct 18 ms 2808 KB Output is correct
30 Correct 4 ms 2644 KB Output is correct
31 Correct 2 ms 2644 KB Output is correct
32 Correct 4 ms 2644 KB Output is correct
33 Execution timed out 3058 ms 8116 KB Time limit exceeded
34 Halted 0 ms 0 KB -