oj.uz

Submission #256179

# Submission time Handle Problem Language Result Execution time Memory
256179 2020-08-02T10:58:23 Z giorgikob Mousetrap (CEOI17_mousetrap) C++14
25 / 100
 1933 ms 64632 KB 
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

const int N = 1e6 + 5;

int n, m, t;
int w[N], P[N];
vector<int> gr[N];
vector<pair<int,int>> L;
vector<int> path;

void dfs(int x, int p){
        P[x] = p;
        for(auto to : gr[x]){
                if(to == p) continue;
                dfs(to, x);
        }
}

int CNT;

void count_w(int x, int cnt, int dep){

        if(gr[x].size() == 1){
                w[x] = cnt + dep;
                return ;
        }
        cnt += gr[x].size() - 2;
        vector<int>v;
        for(int to : gr[x]){
                if(to == P[x]) continue;
                count_w(to, cnt, dep+1);
                v.pb(w[to]);
        }
        cnt -= gr[x].size() - 2;
        sort(v.rbegin(),v.rend());
        if(v.size() == 1){
                w[x] = 1 + dep + cnt;
        } else {
                w[x] = v[1];
        }
}

inline bool check(int x){
        int B = 0;
        for(int i = 0; i < L.size(); i++){
                auto p = L[i];
                //if(i == L.size() - 1) return p.ss + B <= x;
                if(B >= p.ff){
                        if(p.ss + B > x) return false;
                } else
                if(p.ss + B > x){
                        B++;
                }
                if(B > x) return false;
        }

        return true;
}

int main(){

        cin >> n >> t >> m;

        for(int i = 1; i < n; i++){
                int x, y;
                cin >> x >> y;
                gr[x].pb(y);
                gr[y].pb(x);
        }

        dfs(t,0);

        int ver = m;
        while(ver != t){
                path.pb(ver);
                ver = P[ver];
        }

        reverse(path.begin(), path.end());

        for(int i = 0; i < path.size(); i++){
                int x = path[i];
                int k = 3;
                if(i == path.size() - 1) k--;
                CNT += max(0, (int)gr[x].size() - k);
                for(int to : gr[x]){
                        if(to == P[x]) continue;
                        if(path.size() - 1 != i && to == path[i+1]) continue;
                        count_w(to, CNT, 1);
                        L.pb({path.size() - i, w[to]});
                }
                CNT++;
        }


        //for(int i = 1; i <= n; i++) cout << w[i] << " "; cout << endl;

        sort(L.begin(), L.end());

        //for(auto p : L) cout << p.ff << " " << p.ss << endl;

        int l = 0, r = 1e6, answer = -1;
        while(l <= r) {
                int mid = l+r; mid >>= 1;
                if(check(mid)){
                        answer = mid;
                        r = mid - 1;
                } else {
                        l = mid + 1;
                }
        }

        cout << answer << endl;

}

Compilation message

mousetrap.cpp: In function 'bool check(int)':
mousetrap.cpp:50:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < L.size(); i++){
                        ~~^~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:86:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < path.size(); i++){
                        ~~^~~~~~~~~~~~~
mousetrap.cpp:89:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(i == path.size() - 1) k--;
                    ~~^~~~~~~~~~~~~~~~~~
mousetrap.cpp:93:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         if(path.size() - 1 != i && to == path[i+1]) continue;
                            ~~~~~~~~~~~~~~~~^~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 14 ms 23808 KB Output is correct
3 Correct 18 ms 23808 KB Output is correct
4 Correct 18 ms 23716 KB Output is correct
5 Correct 18 ms 23808 KB Output is correct
6 Correct 15 ms 23808 KB Output is correct
7 Incorrect 18 ms 23808 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1091 ms 63324 KB Output is correct
2 Correct 995 ms 59332 KB Output is correct
3 Correct 1933 ms 64632 KB Output is correct
4 Correct 853 ms 44436 KB Output is correct
5 Correct 1692 ms 64504 KB Output is correct
6 Correct 1785 ms 64504 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 14 ms 23808 KB Output is correct
3 Correct 18 ms 23808 KB Output is correct
4 Correct 18 ms 23716 KB Output is correct
5 Correct 18 ms 23808 KB Output is correct
6 Correct 15 ms 23808 KB Output is correct
7 Incorrect 18 ms 23808 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 14 ms 23808 KB Output is correct
3 Correct 18 ms 23808 KB Output is correct
4 Correct 18 ms 23716 KB Output is correct
5 Correct 18 ms 23808 KB Output is correct
6 Correct 15 ms 23808 KB Output is correct
7 Incorrect 18 ms 23808 KB Output isn't correct
8 Halted 0 ms 0 KB -