oj.uz

Submission #1087420

# Submission time Handle Problem Language Result Execution time Memory
1087420 2024-09-12T16:25:21 Z smile Torrent (COI16_torrent) C++14
100 / 100
 263 ms 34252 KB 
#include <bits/stdc++.h>

#define smile "TDL."
#define mp make_pair

using namespace std;
typedef pair<int, int> ii;
typedef long long ll;
const int N = (int) 3e5 + 10;

int n, m;
vector<int> g[N];
int M[3];
int f[N];
int c[N];
ii banned = mp(0,0);

void dfs(int u, int pre)
{
    vector<int> tmp;
    f[u] = 0;
    c[u] = 0;
    for (int v: g[u])
    {
        if (v == pre || mp(min(u, v), max(u, v)) == banned) continue;
        dfs(v, u);
        c[u]++;
        tmp.push_back(f[v]);
    }
    sort(tmp.begin(), tmp.end(), greater<int>());
    for (int i = 0; i < tmp.size(); i++)
        f[u] = max(f[u], tmp[i]+i+1);
}

namespace SUB2
{
    void solve()
    {
        dfs(M[0], M[0]);
        cout << f[M[0]];
    }
}

namespace SUB4
{
    int trace[N];
    void bfs(int s, int t)
    {
        queue<int> q;
        q.push(s);
        trace[s] = -1;
        while (!q.empty())
        {
            int u = q.front(); q.pop();
            for (int v: g[u])
            {
                if (!trace[v])
                {
                    trace[v] = u;
                    q.push(v);
                    if (v == t) return;
                }
            }
        }
    }
    vector<ii> e;
    vector<int> tmp;
    int calc(int u, int v)
    {
        banned = mp(min(u, v), max(u,v));
        dfs(M[1], M[1]);
        dfs(M[0], M[0]);
        cerr << "cute";
        int t1 = f[M[0]], t2 = f[M[1]];
        if (t1 < t2)
            t1 += (c[M[0]] == t1);    
        else if (t2 < t1)
            t2 += (c[M[1]] == t2);
        else if (c[M[0]] == t1 && c[M[1]] == t2)
            t1++;
        return max(t1, t2);
    }
    int ans = INT_MAX;
    bool ok()
    {
        dfs(M[1], M[1]);
        dfs(M[0], M[0]);
        int t1 = f[M[0]], t2 = f[M[1]];
        if (t1 < t2)
            t1 += (c[M[0]] == t1);    
        else if (t2 < t1)
            t2 += (c[M[1]] == t2);
        else if (c[M[0]] == t1 && c[M[1]] == t2)
            t1++;
        ans = min(ans, max(t1, t2));
        return t1 < t2;
    }
    void T()
    {
        int tl = calc(tmp[0], tmp[1]),
            tr = calc(tmp[tmp.size()-2], tmp[tmp.size()-1]);
        int l = 1, r = tmp.size()-2;  
        /*
        for (int i = 17; i >= 0; i--)
        {
            if (l + (1 << i) > r) continue;
            int j = l + (1 << i);
            int u = tmp[j], v = tmp[j-1];
            if (calc(u, v) == tl) l += (1 << i);
        }
        for (int i = 17; i >= 0; i--)
        {
            if (r - (1 << i) < l) continue;
            int j = r - (1 << i);
            int u = tmp[j], v = tmp[j+1];
            if (calc(u, v) == tr) r -= (1 << i);    
        }
        for (int i = 17; i >= 0; i--)
        {
            if (l + (1 << i) > r) continue;
            int j = l + (1 << i);
            int s = tmp[j-1], u = tmp[j], v = tmp[j+1];
            if (calc(s, u) > calc(u, v)) l += (1 << i);    
        }
        for (int i = 17; i >= 0; i--)
        {
            if (l + (1 << i) > r) continue;
            int j = r - (1 << i);
            int s = tmp[j-1], u = tmp[j], v = tmp[j+1];
            if (calc(s, u) < calc(u, v)) r -= (1 << i);    
        }
        for (int i = l-1; i <= r; i++)
            ans = min(ans, calc(tmp[i], tmp[i+1]));
        */
        while (l <= r)
        {
            int m = (l + r) >> 1;
            banned = mp(min(tmp[m], tmp[m-1]), max(tmp[m], tmp[m-1]));
            if (ok())
                l = m + 1;
            else
                r = m - 1;
        }
        // cout << l << ' ' << r << '\n';
        cout << ans;
    }
    void solve()
    {
        int ans = INT_MAX;
        bfs(M[0], M[1]);
        int v = M[1];
        while (v != -1)
        {
            tmp.push_back(v);
            v = trace[v];
        }
        reverse(tmp.begin(), tmp.end());
        T();
    }
}

int main()
{
    // freopen(smile"inp", "r", stdin);
    // freopen(smile"out", "w", stdout);
    // time_t bg = clock();
    cin.tie(0) -> sync_with_stdio(0);   
    cin >> n >> M[0] >> M[1];
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);        
    }
    // cin >> m;   
    // for (int i = 0; i < m; i++)
    //     cin >> M[i];
    // if (m == 1)
    //     SUB2::solve();
    // else
        SUB4::solve();
    
    // cerr << '\n' << setprecision(5) << fixed << (double) (clock() - bg) / CLOCKS_PER_SEC;
    return 0;
}

Compilation message

torrent.cpp: In function 'void dfs(int, int)':
torrent.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i = 0; i < tmp.size(); i++)
      |                     ~~^~~~~~~~~~~~
torrent.cpp: In function 'void SUB4::T()':
torrent.cpp:100:13: warning: unused variable 'tl' [-Wunused-variable]
  100 |         int tl = calc(tmp[0], tmp[1]),
      |             ^~
torrent.cpp:101:13: warning: unused variable 'tr' [-Wunused-variable]
  101 |             tr = calc(tmp[tmp.size()-2], tmp[tmp.size()-1]);
      |             ^~
torrent.cpp: In function 'void SUB4::solve()':
torrent.cpp:149:13: warning: unused variable 'ans' [-Wunused-variable]
  149 |         int ans = INT_MAX;
      |             ^~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7516 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 4 ms 7516 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 28756 KB Output is correct
2 Correct 254 ms 31824 KB Output is correct
3 Correct 235 ms 31980 KB Output is correct
4 Correct 263 ms 34252 KB Output is correct
5 Correct 234 ms 28584 KB Output is correct
6 Correct 231 ms 28508 KB Output is correct
7 Correct 237 ms 34068 KB Output is correct