/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef __int128 vll;
typedef long long ftyp;
typedef std::complex<ftyp> vec;
#define llll std::pair<ll , ll>
#define pb push_back
#define fi first
#define sec second
#define cx real
#define cy imag
#define all(a) a.begin() , a.end()
#define debug std::cout << "!!ALERT ALERT!!" << std::endl;
const ll limit = 1e18+7;
const ll sus = 2e5+5;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
ll n;std::vector<ll> adj[sus];
ll vis[sus] , kd = -1 , cyc[sus];
llll val[sus];
struct nd{
ll cc = 0;
ll l = -1,r = -1;
};
ll ots = 1;
nd valt[sus * 5];
void add(ll nt , ll upd , ll l , ll r , ll a){
if(l == r){
valt[a].cc += upd;
return;
}
ll md = (l + r)/2;
if(md >= nt){
if(valt[a].l == -1){
valt[a].l = ots++;
}
add(nt , upd , l , md , valt[a].l);
}
else{
if(valt[a].r == -1){
valt[a].r = ots++;
}
add(nt , upd , md+1 , r , valt[a].r);
}
valt[a].cc += upd;
}
llll fm(ll l , ll r , ll a){
ll md = (l + r)/2;
if(l == r){
return{l , valt[a].cc};
}
if(valt[a].r != -1 && valt[valt[a].r].cc > 0){
return fm(md+1 , r , valt[a].r);
}
return fm(l , md , valt[a].l);
}
std::vector<ll> v;
void cycdfs(ll crt , ll prv){
vis[crt] = 1;
for(auto j:adj[crt]){
if(j != prv){
if(vis[j] == 1){
kd = j;
}
else if(vis[j] == 0){
cycdfs(j , crt);
}
if(kd != -1){
if(kd == -2){
return;
}
cyc[crt] = 1;
if(kd == crt){
kd = -2;
}
return;
}
}
}
vis[crt] = 2;
}
void svcyc(ll crt , ll prv){
v.pb(crt);
vis[crt] = 1;
for(auto j:adj[crt]){
if(cyc[j] == 1 && vis[j] == 0){
svcyc(j , crt);
return;
}
}
}
llll findep(ll crt , ll prv){
llll cmx = {0 , 1};
for(auto j:adj[crt]){
if(j != prv && cyc[j] == 0){
llll a = findep(j , crt);
a.fi++;
if(cmx.fi > a.fi){
cmx = a;
}
else if(cmx.fi == a.fi){
cmx.sec += a.sec;
}
}
}
return cmx;
}
void solve(){
std::cin >> n;
for(ll i=0;n>i;i++){
ll x , y;std::cin >> x >> y;
adj[x].pb(y);
adj[y].pb(x);
}
cycdfs(1 , -1);
memset(vis , 0 , sizeof(vis));
for(ll i = 1;n>=i;i++){
if(cyc[i] == 1){
svcyc(i , -1);
break;
}
}
for(auto j:v){
val[j] = findep(j , -1);
}
ll cc = v.size()/2 - (v.size()%2==0?1:0);
ll ko = v.size() , cs = 0;
std::cout << cc << "\n";
std::queue<llll> qu;
for(ll i = 0;cc>i;i++){
add(val[ko-i].fi+n+i+1,val[ko-i].sec,0,sus*2,0);
qu.push({val[ko-i].fi+n , val[ko-i].sec + i + 1});
}
for(ll i = 0;1>i;i++){
llll a = fm(0 , 2*sus , 0);
std::cout << a.fi << " " << a.sec << "\n";
}
return;/**/
}
int main(){
std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("in.txt" , "r" , stdin);
freopen("out.txt" , "w" , stdout);
#endif
ll t = 1;
//std::cin >> t;
while(t--){
solve();
}
}
Compilation message
shymbulak.cpp:5:78: warning: "/*" within comment [-Wcomment]
5 | #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
|
shymbulak.cpp: In function 'void solve()':
shymbulak.cpp:132:22: warning: unused variable 'cs' [-Wunused-variable]
132 | ll ko = v.size() , cs = 0;
| ^~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:148:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
148 | freopen("in.txt" , "r" , stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
shymbulak.cpp:149:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
149 | freopen("out.txt" , "w" , stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
6612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
6612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
6612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
