Submission #968561

#	Time	Username	Problem	Language	Result	Execution time	Memory
968561		Hadi_Alhamed	Burza (COCI16_burza)	C++17	0 / 160	1 ms	600 KiB

burza

//to live is to die
#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;

typedef long long int ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpl;
#define Clear(a, n)              \
    for (int i = 0; i <= n; i++) \
    {                            \
        a[i] = 0;                \
    }
#define clearMat(a, n, m, d)         \
    for (int i = 0; i <= n; i++)     \
    {                                \
        for (int j = 0; j <= m; j++) \
            a[i][j] = d;             \
    }
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define PB push_back
#define PF push_front
#define MP make_pair
#define F first
#define S second
#define rep(i, n) for (int i = 0; i < n; i++)
#define repe(i, j, n) for (int i = j; i < n; i++)
#define SQ(a) (a) * (a)
#define rep1(i, n) for (int i = 1; i <= n; i++)
#define Rrep(i, start, finish) for (int i = start; start >= finish; i--)
#define db(x)  cerr << #x <<" "; _print(x); cerr << endl;

#define forn(i, Start, End, step) for (int i = Start; i <= End; i += step)
#define rforn(i, Start, End, step) for (int i = Start; i >= End; i -= step)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
// ll arr[SIZE];
/*
how to find n % mod ; n < 0?
x = (n+mod)%mod
if(x < 0) x += mod;
*/
void _print(int x)
{
    cerr << x;
}
void _print(ll x)
{
    cerr << x;
}
void _print(string x)
{
    cerr << x;
}
void _print(char x)
{
    cerr << x;
}
void _print(double x)
{
    cerr << x;
}
void _print(ull x)
{
    cerr << x;
}
void _print(vl x)
{
    for(auto e : x)
    {
        cerr << e << " ";
    }
    cerr << "\n";
}
void print(vpi x)
{
    for(auto e : x)
    {
        cerr << e.F << " " << e.S << "\n";
    }
    cerr << "\n";
}
void _print(vi x)
{
    for(auto e : x)
    {
        cerr << e << " ";
    }
    cerr << "\n";
}

void _print(deque<ll>x)
{
    for(auto e : x)
    {
        cerr << e << " ";
    }
    cerr << "\n";
}

//order_of_key(k): # of elements less than k (which is the index of x = k)
//find_by_order(k); iterator of the k-th element


template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<T, null_type,  less_equal <T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> bool ckmin(T& a, const T& b)
{
    return b<a?a=b,1:0;
}
template<class T> bool ckmax(T& a, const T& b)
{
    return a<b?a=b,1:0;
}
template<typename T> istream& operator>>(istream& in, vector<T>& a)
{
    for(auto &x : a) in >> x;
    return in;
};
template<typename T> ostream& operator<<(ostream& out, vector<T>& a)
{
    for(auto &x : a) out << x << ' ';
    return out;
};

// priority_queue<data type , the container that would hold the values , greater<pair<int,int>>>
// greater means that we want the smallest value on top
// less means that we want the largest
// x ^ (n) mod m = ( (x mod m)^(n) ) mod m
char to_char(int num)
{
    return (char)(num + '0');
}

ll const MAX = 1e18+1;
ll const oo = 1e18 + 1;
ll const INF = 1e9 + 10;
const ll MOD = 1e9 + 7;
ll const SIZE = 2e5 + 900;
//const int MAX_N = 100'005;
const int LOG = 20;
template<typename T , typename T2>
void add(T & X, T2 Y)
{
    X = (X + Y + MOD)%MOD;
}

template<typename T , typename T2>
T mult(T X, T2 Y)
{
    return X * Y % MOD;
}

void setIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}
ll dp0[404] , dp1[404];
bool vis[404];
int dist[404];
void solve()
{

    /*
        any node that has a distance of at least 1 from node 1
        and has two sons at most
        we can cut the road for it

        len of path_to_U + 1 >= sons of U

    */
    int N , K;
    cin >> N >> K;
    vector<int>adj[N + 2];

    //dp0[node] = if i chose node to cut what is his best choices to take out of the other adj of par
    //dp0[node] = 1 + max(dp1[adj_nodes]);


    //dp1[node] = for node as a parent what is the answer if we choose best son to cut
    //dp1[node] = min(dp[sons][0]);

    rep(i , N - 1)
    {
        int from , to;
        cin >> from >> to;
        adj[from].PB(to);
        adj[to].PB(from);
    }
    function<void(int , int , int)> _DFS = [&] (int node , int par , int dis)->void
    {
        dist[node] = dis;
        for(int& to : adj[node])
        {
            if(to == par)continue;
            dist[to] = dis + 1;
            _DFS(to , node , dis + 1);
        }
    };
    function<void(int , int)> DFS = [&](int node ,int par)->void
    {
        vis[node] = 1;
        for(int & cut : adj[node])
        {
            if(cut == par)continue;
            if(vis[cut])
            {
                dp1[par] = min(dp1[par] , dp0[cut]);
                continue;
            }
            //chose cut as a node to cut there
            for(int& go : adj[node])
            {
                if(go == par || go == cut)continue;
                if(!vis[go])
                {
                    DFS(go , node);
                }
                dp0[cut] = max(dp0[cut] , dp1[go]);
            }
            dp1[par] = min(dp1[par] , dp0[cut]);
        }
    };
    _DFS(1 , 0 ,  0);
    for(int i = 0 ; i < N + 2 ; i++)
    {
        dp0[i] = dist[i];
        dp1[i] = 1e9;
    }
    DFS(1 , 0);
    int mx = dp1[1];
    if(mx <= K)
    {
        cout << "DA\n";
    }else{
        cout << "NE\n";
    }

}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    setIO("guard");

    int T = 1;
//    cin >> T;
    while(T--)
    {
        solve();
    }
    return 0;
}

/* stuff you should look for
 * WRITE STUFF DOWN,  ON PAPER
 * BFS THEN DFS
 * int overflow, array bounds
 * special cases (n=1?)
 * do sm th instead of nothing and stay organized
 * DON'T GET STUCK ON ONE APPROACH
 * (STUCK?)******** Try to simplify the problem(keeping in mind the main problem), ():
 * 1- problem to subProblem
 * 2- from simple to complex: start with a special
 *    problem and then try to update the solution for general case
 *    -(constraints - > solve it with none , one,two ... of them till you reach the given problem
      -(no constraints - > try to give it some)
      -how a special case may be incremented
 * 3-Simplification by Assumptions
 * REVERSE PROBLEM
 * PROBLEM ABSTRACTION
 * SMALL O BSERVATIONS MIGHT HELP ALOT
 * WATCH OUT FOR TIME
 * RETHINK YOUR IDEA,BETTER IDEA, APPROACH?
 * CORRECT IDEA, NEED MORE OBSERVATIONS
 * CORRECT APPROACH, WRONG IDEA
 * WRONG APPROACH
 * THINK CONCRETE THEN SYMBOL,
 * having the solution for the first m state , can we solve it for m + 1 ?
 * in many cases incremental thinking needs data sorting
 */

Compilation message (stderr)

burza.cpp: In function 'void setIO(std::string)':
burza.cpp:165:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
burza.cpp:166:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 16
• Subtask 3: 0 / 16
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16