Submission #1087410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087410		smile	Torrent (COI16_torrent)	C++14	0 / 100	57 ms	23124 KiB

torrent

#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);
vector<int> V0, V1;
void dfs(int u, int pre)
{
    vector<int> tmp;
    f[u] = 0;
    c[u] = 0;
    for (int v: g[u])
    {
        if (v == pre) continue;
        dfs(v, u);
        c[u]++;
        tmp.push_back(f[v]);
        if (u == M[0]) V0.push_back(f[v]);
        if (u == M[1]) V1.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;
                }
            }
        }
    }
    int calc(vector<int> v0, vector<int> v1, int len1, int len2)
    {
        v0.push_back(len1); sort(v0.begin(), v0.end(), greater<int>());
        v1.push_back(len2); sort(v1.begin(), v1.end(), greater<int>());
        // optimize tgian
        f[M[0]] = f[M[1]] = 0;
        for (int i = 0; i < v0.size(); i++) f[M[0]] = max(f[M[0]], v0[i]+i+1);
        for (int i = 0; i < v1.size(); i++) f[M[1]] = max(f[M[1]], v1[i]+i+1);
        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);
    }
    void solve()
    {
        int ans = INT_MAX;
        bfs(M[0], M[1]);
        vector<int> tmp;
        int v = M[1];
        int cnt = 0;
        // cerr << trace[v];
        while (v != -1)
        {
            tmp.push_back(v);
            v = trace[v];
            // cerr << ++cnt << ' ' << v << " ok\n";
        }
        reverse(tmp.begin(), tmp.end());
        for (int i = 1; i < tmp.size(); i++)
        {
 
            // banned = mp(min(tmp[i-1], tmp[i]), max(tmp[i-1], tmp[i]));
            ans = min(ans, calc(V0, V1, i, tmp.size()-i-1));
 
        }
        cout << ans;
    }
}
int main()
{
  //  freopen(smile"inp", "r", stdin);
    //freopen(smile"ans", "w", stdout);
    cin.tie(0) -> sync_with_stdio(0);   
    //auto bg = clock();
    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);        
    }
    SUB4::solve();
//    cerr << '\n' << setprecision(5) << fixed << (double) (clock() - bg) / CLOCKS_PER_SEC;
    
    return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'void dfs(int, int)':
torrent.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0; i < tmp.size(); i++)
      |                     ~~^~~~~~~~~~~~
torrent.cpp: In function 'int SUB4::calc(std::vector<int>, std::vector<int>, int, int)':
torrent.cpp:75:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for (int i = 0; i < v0.size(); i++) f[M[0]] = max(f[M[0]], v0[i]+i+1);
      |                         ~~^~~~~~~~~~~
torrent.cpp:76:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (int i = 0; i < v1.size(); i++) f[M[1]] = max(f[M[1]], v1[i]+i+1);
      |                         ~~^~~~~~~~~~~
torrent.cpp: In function 'void SUB4::solve()':
torrent.cpp:101:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for (int i = 1; i < tmp.size(); i++)
      |                         ~~^~~~~~~~~~~~
torrent.cpp:92:13: warning: unused variable 'cnt' [-Wunused-variable]
   92 |         int cnt = 0;
      |             ^~~

• Subtask 1: 0 / 31
• Subtask 2: 0 / 69