Submission #733627

#	Time	Username	Problem	Language	Result	Execution time	Memory
733627		n0sk1ll	Cats or Dogs (JOI18_catdog)	C++17	38 / 100	3058 ms	8116 KiB

catdog

#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 / 8
• Subtask 2: 30 / 30
• Subtask 3: 0 / 62