oj.uz

Submission #599427

# Submission time Handle Problem Language Result Execution time Memory
599427 2022-07-19T14:01:53 Z Andyvanh1 Wells (CEOI21_wells) C++14
0 / 100
 1 ms 472 KB 
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <iomanip>
#include <queue>
#include <stack>



using namespace std;

#define vt vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define FORR1(x) for(int i = 0; i < (x); i++)
#define FORR2(i,x) for (int (i) = 0; (i) < (x); (i)++)
#define MOD 1000000007

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef long double ld;
typedef vt<int> vi;
typedef pair<int,pair<int,int>> piii;

struct fwtree{
    vi arr;
    int sz;

    void init(int n){
        arr.resize(n+1);
        sz = n;
        FORR1(n+1)arr[i] = 0;
    }

    //remember difference between 0- and 1- indexing
    void add(int index, int val){
        while(index <= sz){
            arr[index]+=val;
            index+=index&-index;
        }
    }

    ll get(int index){
        ll val = 0;
        while(index!=0){
            val+=arr[index];
            index-=index&-index;
        }
        return val;
    }

    ll get(int l, int r){
        return get(r)-get(l-1);
    }

};

int N, O, M;
vi ceo;
ll fastexp(ll n, int m){
    if(m==0)return 1;
    ll cur = fastexp(n,m/2);
    cur = cur*cur;
    cur%=MOD;
    if(m&1){
        cur*=n;
        cur%=MOD;
    }
    return cur;
}

ll inv(ll x){
    return fastexp(x,MOD-2);
}



vt<vi> adjlist;
int degree[200005];
int dist[205][205];
int cur;

void dfs(int node, int par){
    for(auto& e: adjlist[node]){
        if(e!=par){
            dist[cur][e] = dist[cur][node]+1;
            dfs(e,node);
        }
    }
}


void solve(){
    int n,k;
    cin>>n>>k;
    adjlist.resize(n);
    FORR1(n-1){
        int u, v;
        cin>>u>>v;
        u--;v--;
        adjlist[u].pb(v);adjlist[v].pb(u);
    }
    FORR1(n){
        cur = i;
        dist[i][i] = 0;
        dfs(i,-1);
    }
    bool x = false;
    int ans = -1;
    FORR1(n){
        bool y = true;
        FORR2(j,n){
            FORR2(l,n){
                if(dist[j][l]==k-1){
                    int a = dist[i][j];
                    int b = dist[i][l];
                    int c = (a+b-k+1)>>1;
                    if((max(a,b)/k)*k<c){
                        y = false;
                        break;
                    }else{
                        if((min(a,b)/k)*k>=c&&c%k!=0){
                            y = false;
                            break;
                        }
                    }

                }
            }
            if(!y)break;
        }
        if(y){
            ans = i;
            x=true;
            break;
        }
    }
    cout<<(x ? "YES\n":"NO\n");
    cout<<ans;


    


}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

Compilation message

wells.cpp: In function 'void solve()':
wells.cpp:19:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   19 | #define FORR2(i,x) for (int (i) = 0; (i) < (x); (i)++)
      |                             ^
wells.cpp:116:9: note: in expansion of macro 'FORR2'
  116 |         FORR2(j,n){
      |         ^~~~~
wells.cpp:19:29: warning: unnecessary parentheses in declaration of 'l' [-Wparentheses]
   19 | #define FORR2(i,x) for (int (i) = 0; (i) < (x); (i)++)
      |                             ^
wells.cpp:117:13: note: in expansion of macro 'FORR2'
  117 |             FORR2(l,n){
      |             ^~~~~

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Partially correct 1 ms 468 KB Output is partially correct
3 Partially correct 1 ms 460 KB Output is partially correct
4 Partially correct 1 ms 468 KB Output is partially correct
5 Partially correct 1 ms 468 KB Output is partially correct
6 Partially correct 1 ms 456 KB Output is partially correct
7 Partially correct 1 ms 468 KB Output is partially correct
8 Partially correct 1 ms 456 KB Output is partially correct
9 Partially correct 1 ms 460 KB Output is partially correct
10 Partially correct 1 ms 468 KB Output is partially correct
11 Correct 1 ms 468 KB Output is correct
12 Partially correct 1 ms 468 KB Output is partially correct
13 Partially correct 1 ms 468 KB Output is partially correct
14 Partially correct 1 ms 460 KB Output is partially correct
15 Partially correct 1 ms 468 KB Output is partially correct
16 Partially correct 1 ms 468 KB Output is partially correct
17 Partially correct 1 ms 468 KB Output is partially correct
18 Partially correct 1 ms 468 KB Output is partially correct
19 Partially correct 1 ms 468 KB Output is partially correct
20 Partially correct 1 ms 472 KB Output is partially correct
21 Partially correct 1 ms 464 KB Output is partially correct
22 Partially correct 1 ms 464 KB Output is partially correct
23 Partially correct 1 ms 468 KB Output is partially correct
24 Partially correct 1 ms 468 KB Output is partially correct
25 Partially correct 1 ms 468 KB Output is partially correct
26 Partially correct 1 ms 468 KB Output is partially correct
27 Partially correct 1 ms 468 KB Output is partially correct
28 Partially correct 1 ms 468 KB Output is partially correct
29 Correct 1 ms 468 KB Output is correct
30 Partially correct 1 ms 464 KB Output is partially correct
31 Partially correct 1 ms 460 KB Output is partially correct
32 Partially correct 1 ms 468 KB Output is partially correct
33 Partially correct 1 ms 468 KB Output is partially correct
34 Partially correct 1 ms 456 KB Output is partially correct
35 Partially correct 1 ms 468 KB Output is partially correct
36 Partially correct 1 ms 468 KB Output is partially correct
37 Partially correct 1 ms 468 KB Output is partially correct
38 Partially correct 1 ms 468 KB Output is partially correct
39 Partially correct 1 ms 468 KB Output is partially correct
40 Partially correct 1 ms 472 KB Output is partially correct
41 Partially correct 1 ms 468 KB Output is partially correct
42 Partially correct 1 ms 468 KB Output is partially correct
43 Partially correct 1 ms 460 KB Output is partially correct
44 Partially correct 1 ms 460 KB Output is partially correct
45 Partially correct 1 ms 468 KB Output is partially correct
46 Partially correct 1 ms 468 KB Output is partially correct
47 Partially correct 1 ms 468 KB Output is partially correct
48 Partially correct 1 ms 468 KB Output is partially correct
49 Incorrect 1 ms 456 KB Output isn't correct
50 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Partially correct 1 ms 468 KB Output is partially correct
3 Partially correct 1 ms 460 KB Output is partially correct
4 Partially correct 1 ms 468 KB Output is partially correct
5 Partially correct 1 ms 468 KB Output is partially correct
6 Partially correct 1 ms 456 KB Output is partially correct
7 Partially correct 1 ms 468 KB Output is partially correct
8 Partially correct 1 ms 456 KB Output is partially correct
9 Partially correct 1 ms 460 KB Output is partially correct
10 Partially correct 1 ms 468 KB Output is partially correct
11 Correct 1 ms 468 KB Output is correct
12 Partially correct 1 ms 468 KB Output is partially correct
13 Partially correct 1 ms 468 KB Output is partially correct
14 Partially correct 1 ms 460 KB Output is partially correct
15 Partially correct 1 ms 468 KB Output is partially correct
16 Partially correct 1 ms 468 KB Output is partially correct
17 Partially correct 1 ms 468 KB Output is partially correct
18 Partially correct 1 ms 468 KB Output is partially correct
19 Partially correct 1 ms 468 KB Output is partially correct
20 Partially correct 1 ms 472 KB Output is partially correct
21 Partially correct 1 ms 464 KB Output is partially correct
22 Partially correct 1 ms 464 KB Output is partially correct
23 Partially correct 1 ms 468 KB Output is partially correct
24 Partially correct 1 ms 468 KB Output is partially correct
25 Partially correct 1 ms 468 KB Output is partially correct
26 Partially correct 1 ms 468 KB Output is partially correct
27 Partially correct 1 ms 468 KB Output is partially correct
28 Partially correct 1 ms 468 KB Output is partially correct
29 Correct 1 ms 468 KB Output is correct
30 Partially correct 1 ms 464 KB Output is partially correct
31 Partially correct 1 ms 460 KB Output is partially correct
32 Partially correct 1 ms 468 KB Output is partially correct
33 Partially correct 1 ms 468 KB Output is partially correct
34 Partially correct 1 ms 456 KB Output is partially correct
35 Partially correct 1 ms 468 KB Output is partially correct
36 Partially correct 1 ms 468 KB Output is partially correct
37 Partially correct 1 ms 468 KB Output is partially correct
38 Partially correct 1 ms 468 KB Output is partially correct
39 Partially correct 1 ms 468 KB Output is partially correct
40 Partially correct 1 ms 472 KB Output is partially correct
41 Partially correct 1 ms 468 KB Output is partially correct
42 Partially correct 1 ms 468 KB Output is partially correct
43 Partially correct 1 ms 460 KB Output is partially correct
44 Partially correct 1 ms 460 KB Output is partially correct
45 Partially correct 1 ms 468 KB Output is partially correct
46 Partially correct 1 ms 468 KB Output is partially correct
47 Partially correct 1 ms 468 KB Output is partially correct
48 Partially correct 1 ms 468 KB Output is partially correct
49 Incorrect 1 ms 456 KB Output isn't correct
50 Halted 0 ms 0 KB -

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Partially correct 1 ms 468 KB Output is partially correct
3 Partially correct 1 ms 460 KB Output is partially correct
4 Partially correct 1 ms 468 KB Output is partially correct
5 Partially correct 1 ms 468 KB Output is partially correct
6 Partially correct 1 ms 456 KB Output is partially correct
7 Partially correct 1 ms 468 KB Output is partially correct
8 Partially correct 1 ms 456 KB Output is partially correct
9 Partially correct 1 ms 460 KB Output is partially correct
10 Partially correct 1 ms 468 KB Output is partially correct
11 Correct 1 ms 468 KB Output is correct
12 Partially correct 1 ms 468 KB Output is partially correct
13 Partially correct 1 ms 468 KB Output is partially correct
14 Partially correct 1 ms 460 KB Output is partially correct
15 Partially correct 1 ms 468 KB Output is partially correct
16 Partially correct 1 ms 468 KB Output is partially correct
17 Partially correct 1 ms 468 KB Output is partially correct
18 Partially correct 1 ms 468 KB Output is partially correct
19 Partially correct 1 ms 468 KB Output is partially correct
20 Partially correct 1 ms 472 KB Output is partially correct
21 Partially correct 1 ms 464 KB Output is partially correct
22 Partially correct 1 ms 464 KB Output is partially correct
23 Partially correct 1 ms 468 KB Output is partially correct
24 Partially correct 1 ms 468 KB Output is partially correct
25 Partially correct 1 ms 468 KB Output is partially correct
26 Partially correct 1 ms 468 KB Output is partially correct
27 Partially correct 1 ms 468 KB Output is partially correct
28 Partially correct 1 ms 468 KB Output is partially correct
29 Correct 1 ms 468 KB Output is correct
30 Partially correct 1 ms 464 KB Output is partially correct
31 Partially correct 1 ms 460 KB Output is partially correct
32 Partially correct 1 ms 468 KB Output is partially correct
33 Partially correct 1 ms 468 KB Output is partially correct
34 Partially correct 1 ms 456 KB Output is partially correct
35 Partially correct 1 ms 468 KB Output is partially correct
36 Partially correct 1 ms 468 KB Output is partially correct
37 Partially correct 1 ms 468 KB Output is partially correct
38 Partially correct 1 ms 468 KB Output is partially correct
39 Partially correct 1 ms 468 KB Output is partially correct
40 Partially correct 1 ms 472 KB Output is partially correct
41 Partially correct 1 ms 468 KB Output is partially correct
42 Partially correct 1 ms 468 KB Output is partially correct
43 Partially correct 1 ms 460 KB Output is partially correct
44 Partially correct 1 ms 460 KB Output is partially correct
45 Partially correct 1 ms 468 KB Output is partially correct
46 Partially correct 1 ms 468 KB Output is partially correct
47 Partially correct 1 ms 468 KB Output is partially correct
48 Partially correct 1 ms 468 KB Output is partially correct
49 Incorrect 1 ms 456 KB Output isn't correct
50 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Partially correct 1 ms 468 KB Output is partially correct
3 Partially correct 1 ms 460 KB Output is partially correct
4 Partially correct 1 ms 468 KB Output is partially correct
5 Partially correct 1 ms 468 KB Output is partially correct
6 Partially correct 1 ms 456 KB Output is partially correct
7 Partially correct 1 ms 468 KB Output is partially correct
8 Partially correct 1 ms 456 KB Output is partially correct
9 Partially correct 1 ms 460 KB Output is partially correct
10 Partially correct 1 ms 468 KB Output is partially correct
11 Correct 1 ms 468 KB Output is correct
12 Partially correct 1 ms 468 KB Output is partially correct
13 Partially correct 1 ms 468 KB Output is partially correct
14 Partially correct 1 ms 460 KB Output is partially correct
15 Partially correct 1 ms 468 KB Output is partially correct
16 Partially correct 1 ms 468 KB Output is partially correct
17 Partially correct 1 ms 468 KB Output is partially correct
18 Partially correct 1 ms 468 KB Output is partially correct
19 Partially correct 1 ms 468 KB Output is partially correct
20 Partially correct 1 ms 472 KB Output is partially correct
21 Partially correct 1 ms 464 KB Output is partially correct
22 Partially correct 1 ms 464 KB Output is partially correct
23 Partially correct 1 ms 468 KB Output is partially correct
24 Partially correct 1 ms 468 KB Output is partially correct
25 Partially correct 1 ms 468 KB Output is partially correct
26 Partially correct 1 ms 468 KB Output is partially correct
27 Partially correct 1 ms 468 KB Output is partially correct
28 Partially correct 1 ms 468 KB Output is partially correct
29 Correct 1 ms 468 KB Output is correct
30 Partially correct 1 ms 464 KB Output is partially correct
31 Partially correct 1 ms 460 KB Output is partially correct
32 Partially correct 1 ms 468 KB Output is partially correct
33 Partially correct 1 ms 468 KB Output is partially correct
34 Partially correct 1 ms 456 KB Output is partially correct
35 Partially correct 1 ms 468 KB Output is partially correct
36 Partially correct 1 ms 468 KB Output is partially correct
37 Partially correct 1 ms 468 KB Output is partially correct
38 Partially correct 1 ms 468 KB Output is partially correct
39 Partially correct 1 ms 468 KB Output is partially correct
40 Partially correct 1 ms 472 KB Output is partially correct
41 Partially correct 1 ms 468 KB Output is partially correct
42 Partially correct 1 ms 468 KB Output is partially correct
43 Partially correct 1 ms 460 KB Output is partially correct
44 Partially correct 1 ms 460 KB Output is partially correct
45 Partially correct 1 ms 468 KB Output is partially correct
46 Partially correct 1 ms 468 KB Output is partially correct
47 Partially correct 1 ms 468 KB Output is partially correct
48 Partially correct 1 ms 468 KB Output is partially correct
49 Incorrect 1 ms 456 KB Output isn't correct
50 Halted 0 ms 0 KB -