| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 572125 |
2022-06-03T17:11:14 Z |
MODDI |
Torrent (COI16_torrent) |
C++14 |
|
821 ms |
20616 KB |
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
using namespace std;
int n, a, b;
vi G[300100], sub_size;
void dfs(int at, int parent){
for(auto next : G[at]){
if(next == parent)
continue;
dfs(next, at);
sub_size[at] += sub_size[next];
}
}
int main(){
cin>>n>>a>>b;
a--; b--;
sub_size.resize(n);
for(int i = 0; i < n; i++)
sub_size[i]=1;
for(int i = 0; i < n - 1; i++){
int z, x;
cin>>z>>x;
z--; x--;
G[z].pb(x);
G[x].pb(z);
}
dfs(0, -1);
queue<vi> q;
vi start;
start.pb(a);
start.pb(b);
q.push(start);
bool vis[n];
memset(vis, false, sizeof(vis));
vis[a] = true;
vis[b] = true;
ll time = 0;
while(!q.empty()){
vi state = q.front();
q.pop();
vi next;
for(int i = 0; i < state.size(); i++){
int at = state[i];
int copy = -1, sz = -1;
for(auto next : G[at]){
if(sub_size[next] > sz && !vis[next]){
sz = sub_size[next];
copy = next;
}
}
if(copy != -1){
next.pb(copy);
next.pb(state[i]);
vis[copy] = true;
}
}
if(next.size() != 0)
{
q.push(next);
time++;
}
}
cout<<time<<endl;
}
Compilation message
torrent.cpp: In function 'int main()':
torrent.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int i = 0; i < state.size(); i++){
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
7380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
821 ms |
20616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
