| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 865142 |
2023-10-24T05:57:18 Z |
hehege |
Torrent (COI16_torrent) |
C++14 |
|
22 ms |
13404 KB |
#include <bits/stdc++.h>
using namespace std;
#define pp pair <int, int>
#define mp make_pair
const int N = 1e5 + 9;
int n, m, s1, s2;
vector <int> adj[N];
namespace sub1 {
int cnt[N], res[N];
bool cmp (int A, int B){
return cnt[A] > cnt[B];
}
void dfs1 (int u, int p){
cnt[u] = 1;
for (int i : adj[u]) if (i != p){
dfs1 (i, u);
cnt[u] += cnt[i];
}
sort (adj[u].begin (), adj[u].end (), cmp);
}
void dfs2 (int u, int p, int id){
res[u] = id;
int susge = 0;
for (int i : adj[u]) if (i != p){
susge++;
dfs2 (i, u, id + susge);
}
}
void solve (){
int s1; cin >> s1;
dfs1 (s1, s1);
dfs2 (s1, s1, 0);
int finalres = 0;
for (int i = 1; i <= n; i++) finalres = max (finalres, res[i]);
cout << finalres;
}
}
namespace sub2 {
//int s1, s2;
int trace[N];
int cnt[N], res[2][N];
vector <pp> path2;
bool cmp (int A, int B){
return cnt[A] > cnt[B];
}
void dfs1 (int u, int p){
cnt[u] = 1;
for (int i : adj[u]) if (i != p){
dfs1 (i, u);
cnt[u] += cnt[i];
}
sort (adj[u].begin (), adj[u].end (), cmp);
}
void dfs2 (int type, int u, int p, int id){
res[type][u] = id;
int susge = 0;
for (int i : adj[u]) if (i != p){
susge++;
dfs2 (type, i, u, id + susge);
}
}
void dfs (int u, int p){
trace[u] = p;
if (u == s2) return;
for (int i : adj[u]) if (i != p) dfs (i, u);
}
void del (int u, int v){
vector <int> vec = adj[u];
adj[u].clear ();
for (int i : vec) if (i != v) adj[u].emplace_back (i);
vec = adj[v];
adj[v].clear ();
for (int i : vec) if (i != u) adj[v].emplace_back (i);
}
void add (int u, int v){
adj[u].emplace_back (v);
adj[v].emplace_back (u);
}
pp get (int val){
memset (cnt, 0, sizeof (cnt));
memset (res, 0, sizeof (res));
del (path2[val].first, path2[val].second);
dfs1 (s1, s1);
dfs1 (s2, s2);
dfs2 (0, s1, s1, 0);
dfs2 (1, s2, s2, 0);
int v1 = 0, v2 = 0;
for (int i = 1; i <= n; i++){
v1 = max (v1, res[0][i]);
v2 = max (v2, res[1][i]);
}
add (path2[val].first, path2[val].second);
return mp (v1, v2);
}
void solve (){
//cin >> s1 >> s2;
dfs (s1, -1);
vector <int> path;
int cc = s2;
while (cc != -1){
path.emplace_back (cc);
cc = trace[cc];
}
for (int i = 0; i + 1 < path.size (); i++) path2.emplace_back (mp (path[i], path[i + 1]));
int finalres = N + N + N + N;
int l = 0, r = path2.size (); r--;
while (l <= r){
int mid = l + r >> 1;
pp p = get (mid);
finalres = min (finalres, max (p.first, p.second));
if (p.first > p.second) l = mid + 1;
else r = mid - 1;
}
cout << finalres;
}
}
signed main (){
ios_base::sync_with_stdio (false);
cin.tie (NULL);
cout.tie (NULL);
if (fopen ("TDL.INP", "r")){
freopen ("TDL.INP", "r", stdin);
freopen ("TDL.OUT", "w", stdout);
}
cin >> n >> s1 >> s2;
for (int i = 1, u, v; i < n; i++){
cin >> u >> v;
adj[u].emplace_back (v);
adj[v].emplace_back (u);
}
m=2;
if (m == 1) sub1::solve ();
else sub2::solve ();
}
Compilation message
torrent.cpp: In function 'void sub2::solve()':
torrent.cpp:121:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for (int i = 0; i + 1 < path.size (); i++) path2.emplace_back (mp (path[i], path[i + 1]));
| ~~~~~~^~~~~~~~~~~~~~
torrent.cpp:125:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
125 | int mid = l + r >> 1;
| ~~^~~
torrent.cpp: In function 'int main()':
torrent.cpp:140:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
140 | freopen ("TDL.INP", "r", stdin);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:141:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
141 | freopen ("TDL.OUT", "w", stdout);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
22 ms |
13404 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
