# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
107920 |
2019-04-26T09:18:23 Z |
shash42 |
Network (BOI15_net) |
C++11 |
|
2000 ms |
24056 KB |
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
using namespace std;
const int N=5e5+5;
int n, tmr=0;
vector<int> adj[N], lvlst[N];
vector< pii > ans;
int lv[N], p[N];
struct lvsrt
{
bool operator()(const int &a, const int &b)
{
return lv[a]>lv[b];
}
};
void dfs(int u)
{
for(auto &v: adj[u])
{
if(v!=p[u])
{
p[v]=u;
dfs(v);
lv[u]+=lv[v];
}
}
if(adj[u].size()==1 && u!=1)
{
tmr++;
lv[u]=1;
}
}
int findg(int u)
{
//cout << tmr << " finding g: " << u << endl;
for(auto &v: adj[u])
{
if(lv[v]>tmr/2 && p[u]!=v)
{
return findg(v);
}
}
return u;
}
void findlvs(int u, int subt)
{
for(auto &v: adj[u])
{
if(v!=p[u])
{
p[v]=u;
findlvs(v, subt);
}
}
if(adj[u].size()==1)
{
lvlst[subt].pb(u);
}
}
int main()
{
cin >> n;
for(int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
p[1]=1;
dfs(1);
if(adj[1].size()==1) tmr++;
int g=findg(1);
// cout << g;
sort(adj[g].begin(), adj[g].end(), lvsrt());
memset(p, 0, n+1);
int numsubt=adj[g].size();
for(int i = 0; i < numsubt; i++)
{
p[adj[g][i]]=g;
findlvs(adj[g][i], i);
}
int itr;
for(int i = 0; i < numsubt; i++)
{
itr=i+1;
while(lvlst[i].size())
{
if(ans.size()==tmr/2) break;
while(!lvlst[itr].size())
{
itr++;
if(itr==numsubt) itr=i+1;
}
if(itr>=numsubt) break;
ans.pb(mp(lvlst[i].back(), lvlst[itr].back()));
lvlst[i].pop_back(); lvlst[itr].pop_back();
itr++;
if(itr==numsubt) itr=i+1;
}
}
if(tmr%2)
{
for(int i = 0; i < numsubt; i++)
{
if(lvlst[i].size()) ans.pb(mp(lvlst[i][0], g));
}
}
cout << ans.size() << "\n";
for(auto &v: ans)
{
cout << v.first << " " << v.second << "\n";
}
}
Compilation message
net.cpp: In function 'int main()':
net.cpp:94:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ans.size()==tmr/2) break;
~~~~~~~~~~^~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
23800 KB |
Output is correct |
2 |
Correct |
24 ms |
23808 KB |
Output is correct |
3 |
Correct |
25 ms |
23928 KB |
Output is correct |
4 |
Correct |
25 ms |
23880 KB |
Output is correct |
5 |
Correct |
24 ms |
23808 KB |
Output is correct |
6 |
Correct |
27 ms |
23808 KB |
Output is correct |
7 |
Correct |
25 ms |
23808 KB |
Output is correct |
8 |
Correct |
24 ms |
23808 KB |
Output is correct |
9 |
Correct |
26 ms |
23808 KB |
Output is correct |
10 |
Correct |
25 ms |
23800 KB |
Output is correct |
11 |
Correct |
25 ms |
23808 KB |
Output is correct |
12 |
Correct |
24 ms |
23928 KB |
Output is correct |
13 |
Correct |
25 ms |
23808 KB |
Output is correct |
14 |
Correct |
26 ms |
23876 KB |
Output is correct |
15 |
Correct |
24 ms |
23808 KB |
Output is correct |
16 |
Correct |
25 ms |
23808 KB |
Output is correct |
17 |
Correct |
28 ms |
23800 KB |
Output is correct |
18 |
Correct |
30 ms |
23808 KB |
Output is correct |
19 |
Correct |
31 ms |
23780 KB |
Output is correct |
20 |
Correct |
25 ms |
23808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
23800 KB |
Output is correct |
2 |
Correct |
24 ms |
23808 KB |
Output is correct |
3 |
Correct |
25 ms |
23928 KB |
Output is correct |
4 |
Correct |
25 ms |
23880 KB |
Output is correct |
5 |
Correct |
24 ms |
23808 KB |
Output is correct |
6 |
Correct |
27 ms |
23808 KB |
Output is correct |
7 |
Correct |
25 ms |
23808 KB |
Output is correct |
8 |
Correct |
24 ms |
23808 KB |
Output is correct |
9 |
Correct |
26 ms |
23808 KB |
Output is correct |
10 |
Correct |
25 ms |
23800 KB |
Output is correct |
11 |
Correct |
25 ms |
23808 KB |
Output is correct |
12 |
Correct |
24 ms |
23928 KB |
Output is correct |
13 |
Correct |
25 ms |
23808 KB |
Output is correct |
14 |
Correct |
26 ms |
23876 KB |
Output is correct |
15 |
Correct |
24 ms |
23808 KB |
Output is correct |
16 |
Correct |
25 ms |
23808 KB |
Output is correct |
17 |
Correct |
28 ms |
23800 KB |
Output is correct |
18 |
Correct |
30 ms |
23808 KB |
Output is correct |
19 |
Correct |
31 ms |
23780 KB |
Output is correct |
20 |
Correct |
25 ms |
23808 KB |
Output is correct |
21 |
Correct |
24 ms |
23808 KB |
Output is correct |
22 |
Correct |
27 ms |
24036 KB |
Output is correct |
23 |
Correct |
27 ms |
24056 KB |
Output is correct |
24 |
Correct |
31 ms |
24056 KB |
Output is correct |
25 |
Correct |
29 ms |
23928 KB |
Output is correct |
26 |
Correct |
31 ms |
23928 KB |
Output is correct |
27 |
Execution timed out |
2037 ms |
23928 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
23800 KB |
Output is correct |
2 |
Correct |
24 ms |
23808 KB |
Output is correct |
3 |
Correct |
25 ms |
23928 KB |
Output is correct |
4 |
Correct |
25 ms |
23880 KB |
Output is correct |
5 |
Correct |
24 ms |
23808 KB |
Output is correct |
6 |
Correct |
27 ms |
23808 KB |
Output is correct |
7 |
Correct |
25 ms |
23808 KB |
Output is correct |
8 |
Correct |
24 ms |
23808 KB |
Output is correct |
9 |
Correct |
26 ms |
23808 KB |
Output is correct |
10 |
Correct |
25 ms |
23800 KB |
Output is correct |
11 |
Correct |
25 ms |
23808 KB |
Output is correct |
12 |
Correct |
24 ms |
23928 KB |
Output is correct |
13 |
Correct |
25 ms |
23808 KB |
Output is correct |
14 |
Correct |
26 ms |
23876 KB |
Output is correct |
15 |
Correct |
24 ms |
23808 KB |
Output is correct |
16 |
Correct |
25 ms |
23808 KB |
Output is correct |
17 |
Correct |
28 ms |
23800 KB |
Output is correct |
18 |
Correct |
30 ms |
23808 KB |
Output is correct |
19 |
Correct |
31 ms |
23780 KB |
Output is correct |
20 |
Correct |
25 ms |
23808 KB |
Output is correct |
21 |
Correct |
24 ms |
23808 KB |
Output is correct |
22 |
Correct |
27 ms |
24036 KB |
Output is correct |
23 |
Correct |
27 ms |
24056 KB |
Output is correct |
24 |
Correct |
31 ms |
24056 KB |
Output is correct |
25 |
Correct |
29 ms |
23928 KB |
Output is correct |
26 |
Correct |
31 ms |
23928 KB |
Output is correct |
27 |
Execution timed out |
2037 ms |
23928 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |