| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1087410 |
2024-09-12T16:02:26 Z |
smile |
Torrent (COI16_torrent) |
C++14 |
|
57 ms |
23124 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);
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
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;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
23124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
