Submission #715964

#	Time	Username	Problem	Language	Result	Execution time	Memory
715964		ktkerem	Shymbulak (IZhO14_shymbulak)	C++17	0 / 100	7 ms	6612 KiB

shymbulak

/*#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 (stderr)

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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50