akhauriyash/Code-Regression huggingface dataset:
use std::io::*;
use std::str::FromStr;
#[allow(unused_imports)]
use std::collections::*;

struct Scanner<R: Read> {
    reader: R,
}

#[allow(dead_code)]
impl<R: Read> Scanner<R> {
    fn new(reader: R) -> Scanner<R> {
        Scanner { reader: reader }
    }

    fn safe_read<T: FromStr>(&mut self) -> Option<T> {
        let token = self.reader.by_ref().bytes().map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        if token.is_empty() {
            None
        } else {
            token.parse::<T>().ok()
        }
    }

    fn read<T: FromStr>(&mut self) -> T {
        if let Some(s) = self.safe_read() {
            s
        } else {
            writeln!(std::io::stderr(), "Terminated with EOF").unwrap();
            std::process::exit(0);
        }
    }

    fn vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
        (0..len).map(|_| self.read()).collect()
    }

    fn mat<T: FromStr>(&mut self, row: usize, col: usize) -> Vec<Vec<T>> {
        (0..row).map(|_| self.vec(col)).collect()
    }
}

trait Joinable {
    fn join(self, sep: &str) -> String;
}

impl<U: ToString, T: Iterator<Item=U>> Joinable for T {
    fn join(self, sep: &str) -> String {
        self.map(|x| x.to_string()).collect::<Vec<_>>().join(sep)
    }
}

fn main() {
    std::thread::Builder::new()
        .stack_size(104_857_600)
        .spawn(solve)
        .unwrap()
        .join()
        .unwrap();
}

fn bubble_sort(c: &mut Vec<(char, char, usize)>) {
    let n = c.len();
    for i in 0..n {
        for j in (i+1..n).rev() {
            if c[j].1 < c[j-1].1 {
                c.swap(j, j-1);
            }
        }
    }
}

fn selection_sort(c: &mut Vec<(char, char, usize)>) {
    let n = c.len();
    for i in 0..n {
        let mut minj = i;
        for j in i..n {
            if c[j].1 < c[minj].1 {
                minj = j;
            }
        }
        c.swap(i, minj);
    }
}

fn is_stable(c: &Vec<(char, char, usize)>) -> bool {
    let n = c.len();
    for i in 0..n {
        for j in i+1..n {
            if c[i].1 == c[j].1 && c[i].2 > c[j].2 {
                return false;
            }
        }
    }
    true
}

fn solve() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);

    let n = sc.read();
    let v: Vec<(char, char, usize)> = (0..n).map(|i| {
        let s: String = sc.read();
        let mut it = s.chars();
        let c = it.next().unwrap();
        let k = it.next().unwrap();
        (c, k, i)
    }).collect();

    let mut bsorted = v.clone();
    bubble_sort(&mut bsorted);
    println!("{}", bsorted.iter().map(|&(c, k, _)| format!("{}{}", c, k)).join(" "));
    println!("{}table", if is_stable(&bsorted) { "S" } else { "Not s" });

    let mut ssorted = v.clone();
    selection_sort(&mut ssorted);
    println!("{}", ssorted.iter().map(|&(c, k, _)| format!("{}{}", c, k)).join(" "));
    println!("{}table", if is_stable(&ssorted) { "S" } else { "Not s" });
}



Measured memory_bytes: 9076
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(int)(n); i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  string a, b; cin >> a >> b;
  int ab = stoi(a+b);
  string ans = "No";
  for (int i=2; i*i<=ab; i++) {
    if (i*i == ab) {
      ans = "Yes";
      break;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
using ll = long long;


int main() {
  string S;
  cin >> S;
  if (S == "Sunny") {
    cout << "Cloudy" << endl;
  } else if (S == "Cloudy") {
    cout << "Rainy" << endl;
  } else {
    cout << "Sunny" << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n+1);
  
  for(int i=1;i<102;i++)
    for(int j=1;j<102;j++)
      for(int k=1;k<102;k++){
        int s;
        s = i*i + j*j + k*k + i*j + j*k + k*i;
        if(s<n+1)	a.at(s)+=1;
      }
  
  for(int i=1;i<n+1;i++)
    cout << a.at(i) << endl;
  
  return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)                    \
  for (int i = 0; i < (int)(n); i++) \
    ;

#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  vector<int> count(200000, 0);
  for (int i = 0; i < n; i++) {
    cin >> a.at(i);
  }

  for (int x : a) {
    count.at(x)++;
    if (x - 1 >= 0) {
      count.at(x - 1)++;
    }
    count.at(x + 1)++;
  }
  int count_max = 0;
  for (int x : count) {
    count_max = max(x, count_max);
  }
  cout << count_max << endl;
}


Measured memory_bytes: 1408
#include<stdio.h>
int main()
{
	int i,n;
	int s[1000];
	int a,b,c,d;
	int x,y,z;
	scanf("%d %d %d",&a,&b,&c);
	for(i=0;i<100;i++)
	{
		if(a%2==0&&b%2==0&&c%2==0)
		{
			x=a/2;
			y=b/2;
			z=c/2;
			a=y+z;
			b=x+z;
			c=x+y;
			
			
			
		}
		
		else break;
		
		
	}
	
	n=i;
	if(n==100) printf("-1");
	else printf("%d",n);
	return 0;
	
	
	
	
}

Measured memory_bytes: 256
import scala.collection.mutable

object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val N, M = sc.nextInt()
  val disjointSet = DisjointSet.apply(1.to(N): _*)
  1.to(M).foreach(_ => disjointSet.union(sc.nextInt(), sc.nextInt()))
  println(disjointSet.sets.size - 1)
  
  class DisjointSet[A] {
    
    import DisjointSet.Node
    
    private[this] val parent = mutable.Map.empty[A, Node[A]]

    private[this] implicit def toNode(x: A): Node[A] = {
      assume(contains(x))
      parent(x)
    }

    def contains(x: A): Boolean = parent contains x

    def +=(x: A): Unit = {
      assume(!contains(x))
      parent(x) = new Node(x)
    }

    def union(x: A, y: A): Unit = {
      val (xRoot, yRoot) = (x.root, y.root)
      if (xRoot != yRoot) {
        if (xRoot.rank < yRoot.rank) {
          xRoot.parent = yRoot
        } else if (xRoot.rank > yRoot.rank) {
          yRoot.parent = xRoot
        } else {
          yRoot.parent = xRoot
          xRoot.rank += 1
        }
      }
    }

    def apply(x: A): A = x.root.entry

    def sets: Iterable[Iterable[A]] = parent.keys.groupBy(_.root.entry).values
  }

  object DisjointSet {

    private[DisjointSet] class Node[A](val entry: A) {

      var (parent, rank) = (this, 0)

      def root: Node[A] = {
        if (parent != this) {
          parent = parent.root
        }
        parent
      }
    }

    def empty[A] = new DisjointSet[A]

    def apply[A](elements: A*): DisjointSet[A] = {
      val d = empty[A]
      elements foreach {e => d += e}
      d
    }
  }

}


Measured memory_bytes: 77600
#include<bits/stdc++.h>
using namespace std;

#define mx 100005
#define ll long long

int ar[mx];
char ch[mx];

int n,m,k,ii;

void solve()
{
    int a,b,c;
    cin>>a>>b>>c>>k;
    int cnt=0;
    while(b<=a)
    {
        b*=2;
        cnt++;
    }
    while(c<=b)
    {
        c*=2;
        cnt++;
    }
    if(cnt<=k)
    {
        cout<<"Yes\n";
    }
    else cout<<"No\n";

}

int main()
{
   //freopen("in.txt","r",stdin);
   //freopen("out.txt","w",stdout);
   int t=1;
  // scanf("%d",&t);
   while(t--)solve();
   return 0;
}


Measured memory_bytes: 3632
//#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"

#define rep(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007LL
#define INF (1LL<<60LL)
typedef long long ll;

using namespace std;


int main() {
	ll ans = 0;
	map<string, ll> m;
	ll n, M; cin >> n;
	rep(i, n) {
		string s; cin >> s;
		if (m.find(s) == end(m)) {
			m[s] = 1;
		}
		else m[s] += 1;
	}
	cin >> M;
	rep(i, M) {
		string s; cin >> s;
		if (m.find(s) == end(m)) {
			m[s] = -1;
		}
		else m[s] -= 1;
	}
	for (auto iter = m.begin(); iter != m.end(); iter++) {
		ans = max(ans, iter->second);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

#define N 100001

int vis[N] = {0};
vector<int> g[N];
int dp[N] = {0};

int dfs(int u, int n)
{
	vis[u] = 1;
	int ans = 0;
	for (int v : g[u])
	{
		if (!vis[v])
			ans = max(ans, 1 + dfs(v, n));
		else
			ans = max(ans, 1 + dp[v]);
	}
	return dp[u] = ans;
}

int main()
{
	int n, m;
	cin >> n >> m;
	int x, y;

	for (int i = 0; i < m; i++)
	{
		cin >> x >> y;
		g[x].push_back(y);
	}

	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		if (!vis[i])
		{
			ans = max(ans, dfs(i, n));
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 8576
#include <iostream>
#include <queue>
#include <utility>
using namespace std;
static const int INFTY = (1 << 21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n;
vector<pair<int, int>> adj[100];
int *d;

void dijkstra() {
    priority_queue<pair<int, int>> PQ;
    int d[n], color[n];

    for (int i = 0; i < n; i++) {
        d[i] = INFTY;
        color[n] = WHITE;
    }
    d[0] = 0;
    PQ.push(make_pair(0, 0));

    while (!PQ.empty()) {
        pair<int, int> f = PQ.top();
        PQ.pop();

        int u = f.second;
        color[u] = BLACK;

        if (d[u] < f.first * (-1)) { continue; }

        for (int j = 0; j < adj[u].size(); j++) {
            int v = adj[u][j].first;
            if (color[v] == BLACK) { continue; }
            if (d[u] + adj[u][j].second < d[v]) {
                d[v] = d[u] + adj[u][j].second;
                // printf("d[%d] = %d\n", v, d[v]);
                PQ.push(make_pair(d[v] * (-1), v));
                color[v] = GRAY;
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        printf("%d %d\n", i, d[i]);
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int u, k;
        cin >> u >> k;
        for (int j = 0; j < k; j++) {
            int v, c;
            cin >> v >> c;
            adj[u].push_back(make_pair(v, c));
        }
    }

    dijkstra();

    return 0;
}


Measured memory_bytes: 3248
#include <bits/stdc++.h>
 
#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define reset(a, v) memset((a), v, sizeof(a))
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

const int N = 105;

int n;
int A[N], B[N];

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d %d", &A[i], &B[i]);

	bool ok = false;
	for (int i = 0; i < n-2; i++) {
		if (A[i] == B[i] && A[i+1] == B[i+1] && A[i+2] == B[i+2]) ok = true;
	}
	if (ok) printf("Yes\n");
	else printf("No\n");
	return 0;
}

Measured memory_bytes: 3756
// see https://github.com/LumaKernel/vimfiles/tree/master/snippets/cp-cpp/temp.snip
/// --- .lumrc Template {{{ ///
#if 0
#define assert(...)
#endif
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using P = tuple<ll, ll>;
using P3 = tuple<ll, ll, ll>;
using VI = vector<int>;
using VL = vector<ll>;
using VP = vector<P>;
using VS = vector<string>;

#define omajinai ios::sync_with_stdio(false);cin.tie(0)

#define FOR(i,a,b) for(int i=int(a);i<int(b);++i)
#define FORI(i,a,b) for(int i=int(a);i<=int(b);++i)
#define REP(i,n) FOR(i,0,n)
#define REPI(i,n) FORI(i,0,n)
#define RFOR(i,a,b) for(int i=int(b)-1;i>=int(a);--i)
#define RFORI(i,a,b) for(int i=int(b);i>=int(a);--i)
#define RREP(i,n) RFOR(i,0,n)
#define RREPI(i,n) RFORI(i,0,n)

#define ALL(a) (a).begin(),(a).end()
#define UNIQUE(a) (a).erase(unique(ALL(a)),(a).end())
#define PB push_back
#define EACH(i,c) REP(i,(c).size())
#define REACH(i,c) RREP(i,(c).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(ALL(c))

#define BR cout<<"\n";

#ifdef DEBUG
#define dump(...) cerr<<"["<<__LINE__<< "] "<<#__VA_ARGS__<<" = "<<make_tuple(__VA_ARGS__)<<"\n";
#else
#define dump(...)
#endif

#define YES(x) cout<<((x)?"YES":"NO")<<"\n";
#define Yes(x) cout<<((x)?"Yes":"No")<<"\n";
#define yes(x) cout<<((x)?"yes":"no")<<"\n";

inline int omajinai_int_in(){omajinai;int n;cin>>n;return n;}
inline ll omajinai_ll_in(){omajinai;ll n;cin>>n;return n;}
inline string omajinai_string_in(){omajinai;string n;cin>>n;return n;}
inline int int_in(){int n;cin>>n;return n;}
inline ll ll_in(){ll n;cin>>n;return n;}
inline string string_in(){string n;cin>>n;return n;}
#define oini omajinai_int_in()
#define oinl omajinai_ll_in()
#define oins omajinai_string_in()
#define ini int_in()
#define inl ll_in()
#define ins string_in()

#define isInside(y,x) (0<=(y)&&(y)<h&&0<=(x)&&(x)<w)

#define fi(x) (get<0>(x))
#define se(x) (get<1>(x))
#define th(x) (get<2>(x))
#define fo(x) (get<3>(x))
#define fif(x) (get<4>(x))

template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { o << '{'; EACH(i, v) o << v[i] << (i != v.size()-1 ? ", " : ""); o << "}";  return o; }

template<int n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple<T...> const &){}
template<int n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple<T...> const & t){ os << (n==0?"":", ") << get<n>(t); _ot<n+1>(os, t); }
template<class...T> ostream & operator<<(ostream & os, tuple<T...> const & t){ _ot<0>(os, t); return os; }

template <typename T> inline void smax(T &a, T b) { a = a > b ? a : b; }
template <typename T> inline void smin(T &a, T b) { a = a < b ? a : b; }

constexpr double PI = acos(-1);

/// }}}--- ///

constexpr int INF = 1e9+1;
constexpr ll LINF = 1e18+1;
constexpr int MOD = 1e9+7;

int main() {
int n=ini,a=ini;
Yes((n%500)<=a)
}

//


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
const int inf=1e9;
const ll Inf=1e18;
const int N=1e5+10;
const int mod=0;
int gi() {
    int x=0,o=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
template<typename T> bool chkmax(T &a,T b) { return a<b?a=b,1:0; };
template<typename T> bool chkmin(T &a,T b) { return a>b?a=b,1:0; };
int add(int a,int b) { return a+b>=mod?a+b-mod:a+b; }
int sub(int a,int b) { return a-b<0?a-b+mod:a-b; }
void inc(int &a,int b) { a=(a+b>=mod?a+b-mod:a+b); }
void dec(int &a,int b) { a=(a-b<0?a-b+mod:a-b); }
vector<int> E[N];
int n,m,q,v[N],d[N],c[N],col[N],mx[N];
void dfs(int u,int c,int d) {
    if(mx[u]>=d) return;
    mx[u]=d;
    if(!col[u]) col[u]=c;
    if(!d) return;
    for(int v:E[u]) dfs(v,c,d-1);
}
int main() {
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++) u=gi(),v=gi(),E[u].pb(v),E[v].pb(u);
    cin>>q;
    for(int i=1;i<=q;i++) v[i]=gi(),d[i]=gi(),c[i]=gi();
    memset(mx,-1,sizeof(mx));
    for(int i=q;i;i--) dfs(v[i],c[i],d[i]);
    for(int i=1;i<=n;i++) printf("%d\n",col[i]);
    return 0;
}


Measured memory_bytes: 8440
#%%
n, a, b = map(int, input().split())
s = list(input())

c = 0
d = 0

for i in range(n):
    if s[i] == 'a':
        if c < a+b:
            c += 1
            print('Yes')
        else:
            print('No')
    elif s[i] == 'b':
        if c < a+b:
            if d < b:
                print('Yes')
                c += 1
                d += 1
            else:
                print('No')
        else:
            print('No')
    else:
        print('No')




#%%



Measured memory_bytes: 4712
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

double distance(int a, int b, int c, int d){
    
    double dx = c - a;
    double dy = d - b;
    return pow(dx*dx + dy* dy, 0.5);
}

int main(){
    int n;
    cin >> n;

    vector<int> x(n+1), y(n+1), v(n);
    for (int i = 0; i < n; i++){
        cin >> x[i+1] >> y[i+1];
        v[i] = i + 1;
    }

    double sum_of_dist = 0.0;
    do{
        for (int i = 0; i < n-1; i++) {
            sum_of_dist += distance(x[v[i]], y[v[i]], x[v[i+1]], y[v[i+1]]);
        }
    }while(next_permutation(v.begin(), v.end()));

    double fact = 1.0;
    for (double  i = 2; i <= n; i++){
        fact *= i;
    }

    double ans = sum_of_dist / fact;

    cout << fixed << setprecision(10) << ans << endl;
    return 0;
}



Measured memory_bytes: 640
s = input()

a = 0
b = 0
c = 0

for i in range(3):
    if s[i] == 'a':
        a += 1
    elif s[i] == 'b':
        b += 1
    elif s[i] == 'c':
        c += 1

if a == b and b == c:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3060
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        
        String[] input = br.readLine().split(" ");
        int a = Integer.parseInt(input[0]);
        int b = Integer.parseInt(input[1]);
        int c = Integer.parseInt(input[2]);
        String ans = "NO";
        
        for(int i = 1; i <= b; i++){
            if(a * i % b == c){
                ans = "YES";
                break;
            }
        }
        
        out.println(ans);
        out.close();
        
    }
}

Measured memory_bytes: 32872
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <climits>
#include <set>
#include <map>
#include <stack>
#include <iomanip>
#include <tuple>
#define ll long long
using namespace std;
ll factorial(ll n){
    if(n==0){
        return 1;
    }
    else{
        return n*factorial(n-1);
    }
}

double dist(pair<double,double> a,pair<double,double> b){
	return sqrt(pow((a.first - b.first) ,2) + pow((a.second - b.second),2));
}
//繰り返し自乗法
double ism(double aa,ll p){
    double ap=aa;
    double ans=1;
    while(p>0){
        //cout<<"p="<<p<<",ap="<<ap<<endl;
        if(p&1){//奇数が真
            ans*=ap;
        }
        p/=2;
        ap=ap*ap;
    }
    return ans;

}
//繰り返し自乗法(アマリトリバージョン)
ll ismm(ll aa,ll p,ll m){
    ll ap=aa;
    ll ans=1;
    while(p>0){
        //cout<<"p="<<p<<",ap="<<ap<<endl;
        if(p&1){//奇数が真
            ans=(ans*ap)%m;    
        }
        p/=2;              
        ap=(ap*ap)%m;
    }
    return ans;

}

struct all_init
{
    all_init()
    {
        cout << fixed << setprecision(9);
    }
} All_init;


int main()
{
    string s;
    cin>>s;
    ll ans=0;
    for(ll i=0;i<s.size();i++){
        if(s[i]=='1'){
            ans++;
        }
    }
    cout<<ans<<endl;

    
}


Measured memory_bytes: 256
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
// #define main int main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvpii = vector<vpii>;
template<typename A> using fn = function<A>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int &n) { return n & 1; }
constexpr bool even(const int &n) { return !odd(n); }
void solve();
main { solve(); return 0; }
// clang-format on

void solve() {
  string l, r;
  while (cin >> l >> r, l != "0") {
    int a = 0;
    vc p, q;
    rep(i, 4) {
      if (l[i] == r[i]) {
        a++;
      } else {
        p.pb(l[i]), q.pb(r[i]);
      }
    }
    sort(all(p)), sort(all(q));
    vc r;
    set_intersection(all(p), all(q), back_inserter(r));
    cout << a << ' ' << r.size() << endl;
  }
}

Measured memory_bytes: 2996
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const ll INF = 1e18;
#define pu push
#define pb push_back
#define mp make_pair
#define print(x) cout << (x) << endl;
#define rep(i,n) for(ll i = 0; i < (n); i++)
#define SORT(x) sort(x.begin(),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define fi first
#define sc second

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int K, N;
    cin >> K >> N;
    vector<int> A(N);
    rep(i,N) {
        cin >> A.at(i);
    }
    vector<int> dist(N);
    rep(i,N-1) {
        dist.at(i) = A.at(i+1)-A.at(i);
    }
    dist.at(N-1) = A.at(0) + K - A.at(N-1);
    SORT(dist);
    cout << K - dist.at(N-1) << endl;
}

Measured memory_bytes: 1792
N = int(input())
A=[]
xy=[]
for i in range(N):
    a=int(input())
    A.append(a)
    X = [list(map(int, input().split())) for i in range(a)]
    xy.append(X)
mx=0

for i in range(2**N):
    Z=[0]*N
    flag=0
    for j in range(N):
        if ((i>>j)&1):
            Z[j]=1
    for k in range(N):
        for l in range(A[k]):
            if Z[k]==1:
                if Z[xy[k][l][0]-1]!=xy[k][l][1]:
                    flag=1
    if flag==0:
        mx=max(mx,Z.count(1))
print(mx)



Measured memory_bytes: 74504
(let ((n (read))
    (kyorid (read))
    (ans 0))
    (loop for i below n do
        (let ((x (read))
            (y (read)))
            (if (>= (* kyorid kyorid) (+ (* x x) (* y y)))
            (incf ans))   
        )
    )
    (princ ans)
)

Measured memory_bytes: 76912
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
long gcd(long a,long b){return b?gcd(b,a%b):a;}
long lcm(long a,long b){return a/gcd(a,b)*b;}
 
int main(void){
    long a,b,c,d,l,ans;
    scanf("%ld%ld%ld%ld",&a,&b,&c,&d);
    l = lcm(c,d);
    ans = (b-a+1) - ( b/c - (a-1)/c + b/d - (a-1)/d - b/l + (a-1)/l );
    printf("%ld\n",ans);
    return 0;
}

Measured memory_bytes: 128
N = int(input())
A = list(map(int, input().split()))
S=0
list = [0]*N
list[N-1]=A[N-1]%1000000007
for i in range(N-2,0,-1):
    list[i]=list[i+1]+A[i]%1000000007
    list[i]=list[i]%1000000007
for i in range(N-1):
    S=S+A[i]*list[i+1]%1000000007   
print(S%(1000000007))

Measured memory_bytes: 31592
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
#define repa(i,a,n) for(int i=(a);i<(n);i++)
#define rrep(i,n) for(int i=n;i>=0;i--)
#define rrepa(i,a,n) for(int i=n;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define vc vector

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int,int> pi;

int main(){

    ll n,a,b;cin>>n>>a>>b;

    ll ans;
    if((b-a)%2==0)ans=(b-a)/2;
    else{
        ans=(b+a-1)/2;
        cmin(ans,(2*n-b+1-a)/2);
    }

    cout<<ans<<"\n";

    return 0;

}

Measured memory_bytes: 256
from collections import deque
N,Q = map(int,input().split())
E = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    E[a].append(b)
    E[b].append(a)

d = [0]*(N+1)
visit = [0]*(N+1)
for i in range(Q):
    p,x = map(int,input().split())
    d[p]+=x
def bfs(s):
    q = deque([s])
    while q:
        v = q.pop()
        visit[v] = 1
        for j in E[v]:
            if(visit[j] == 1):
                continue
            q.append(j)
            d[j] += d[v]
            
bfs(1)
for i in range(1,N+1):
    print(d[i])

Measured memory_bytes: 53016
from sys import stdin
from collections import deque
n, e = map(int, stdin.readline().split())
G = [[] for _ in [0] * n]
indeg = [0] * n
out = []
V = [False] * n
def bfs(s):
    dq = deque([s])
    V[s] = True
    while dq:
        u = dq.popleft()
        out.append(u)
        for i in range(len(G[u])):
            v = G[u][i]
            indeg[v] -= 1
            if indeg[v] == 0 and not V[v]:
                V[v] = True
                dq.append(v)
def tsort():
    for u in range(n):
        for i in range(len(G[u])):
            indeg[G[u][i]] += 1
    for u in range(n):
        if indeg[u] == 0 and not V[u]:
            bfs(u)
    for i in range(len(out)):
        print(out[i])
for _ in [0] * e:
    s, t = map(int, stdin.readline().split())
    G[s].append(t)
tsort()

Measured memory_bytes: 11260
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<utility>
#include<string>
#include<stack>
#include<queue>
#include<set>
#include<math.h>
#include <map>
using namespace std;
typedef long long int ll;
#define repi(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,a) repi(i,0,a)
#define all(u) u.begin(),u.end()

ll max(ll a, ll b){
    if (a > b) return a;
    else return b;
}

ll f(ll x, ll y){
    ll res = 0;
    if (x == 0){
        rep(i,50){
            ll num = ((y+1)/ll(pow(2,i+1)))*pow(2,i)+max((((y+1)%ll(pow(2,i+1)))- ll(pow(2,i))),0);
            if (num % 2 == 1){
                res += ll(pow(2,i));
            }
        }
        return res;
    }
    rep(i,50){
        ll num1 = (x/ll(pow(2,i+1)))*pow(2,i)+max(((x%ll(pow(2,i+1)))- ll(pow(2,i))),0);
        ll num2 = ((y+1)/ll(pow(2,i+1)))*pow(2,i)+max((((y+1)%ll(pow(2,i+1)))- ll(pow(2,i))),0);
        if ((num2-num1) % 2 == 1){
            res += ll(pow(2,i));
        }
    }
    return res;
}

int main() {
    ll A,B; scanf("%lld%lld",&A,&B);
    cout << f(A,B)<< endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

char t[77];
int cnt[26];
int z[10010];

int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; ++i) {
    scanf("%s", t);
    ++cnt[t[0] - 'A'];
  }
  int l = 0, r = 10010;
  while (r - l > 1) {
    int s = (l + r) / 2;
    int pos = 0;
    memset(z, 0, sizeof z);
    for (int i = 0; i < 26; ++i) {
      for (int j = 0; j < s && j < cnt[i]; ++j) {
        ++z[pos];
        pos = (pos + 1) % s;
      }
    }
    bool ok = true;
    for (int i = 0; i < s; ++i) {
      if (z[i] < k) {
        ok = false;
      }
    }
    if (ok) {
      l = s;
    } else {
      r = s;
    }
  }
  printf("%d\n", l);
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class t>
using table = vector<vector<t>>;
const ld eps=1e-9;

//// < "d:\d_download\visual studio 2015\projects\programing_contest_c++\debug\a.txt" > "d:\d_download\visual studio 2015\projects\programing_contest_c++\debug\b.answer"

int main() {
	int a, b, n;
	while (cin >> a >> b >> n) {
		a %= b;
		a *= 10;
		int ans = 0;
		for (int i = 0; i < n; ++i) {
			ans += a / b;
			a %= b;
			a *= 10;
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3068
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define mp make_pair
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
const ll INF=1LL<<30;
const ll LINF=1LL<<62;
const double eps=1e-5;
const ll MOD=1000000007LL;
template<typename T>void chmin(T &a,T b){a=min(a,b);};
template<typename T>void chmax(T &a,T b){a=max(a,b);};
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int main(){
	int c[5]={};
	for(int i=0;i<3;i++){
		int a,b;cin>>a>>b;
		c[a]++;
		c[b]++;
	}
	for(int i=1;i<=4;i++){
		if(c[i]>2){
			cout<<"NO"<<endl;
			return 0;
		}
	}
	cout<<"YES"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int N, M, ac, pe, p;
string S;

int main() {
  cin >> N >> M;
  vector<int> wa(N);
  while (M-- && cin >> p >> S && p--) {
    if (wa.at(p) == -1) continue;
    else if (S == "AC") ac++, pe += wa.at(p), wa.at(p) = -1;
    else wa.at(p)++;
  }

  cout << ac << " " << pe << "\n";
}

Measured memory_bytes: 768
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()



def main():
	n=II()

	ans=0
	for i in range(1,10**6+10):
		a=n-i
		if a%i==0:
			b=a//i
			if b>i:
				ans+=b
			else:
				break
	print(ans)



	
	
	



	
	
	









if __name__ == "__main__":
	main()


Measured memory_bytes: 63556
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,M = map(int,input().split())
fac = [1, 1]
inv = [0, 1]
finv = [1, 1]
MOD = 10**9+7
for i in range(2, M+2):
    fac.append(fac[-1] * i % MOD)
    inv.append(MOD - inv[MOD%i] * (MOD//i) % MOD)
    finv.append(finv[-1] * inv[-1] % MOD) 
def comb_mod(n, r, m):  #nCr mod m
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m

def chofuku(n,r): # nHr mod MOD の計算
    return comb_mod(n+r-1,r)
 
def nPr(n,r,m): #nPr mod MOD の計算
    return fac[n]*finv[n-r]%m
ans = 0
for i in range(1,N+1):
    if i % 2 == 1:
        flag = 1
    else:
        flag = -1
    s = flag*comb_mod(N,i,MOD)*nPr(M-i,N-i,MOD)
    ans += s
    if ans > MOD:
        ans %= MOD
ans1 = 1
for i in range(N):
    ans1 *= (M-i)
    ans1 %= MOD
ans2 = (ans1*ans1)%MOD
ans3 = (ans*nPr(M,N,MOD)) %MOD
print((ans2-ans3)%MOD)


Measured memory_bytes: 197640
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int mod = 1e9+7;
const int MAX = 5100000;
const int V = 100005;
ll dy[8] = {1,0,-1,0,1,-1,1,-1};
ll dx[8] = {0,1,0,-1,1,-1,-1,1};
const double pi = acos(-1);
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << endl;}
#define INT_MAX 1e9+7
vector<ll> fac(MAX), finv(MAX), inv(MAX);

int main(){
    ll n,t; cin >> n >> t;
    vpl v(n);
    rep(i,n){
        cin >> v[i].first >> v[i].second;
    }
    sort(all(v));
    vvl dp(n+1,vl(6005,0));
    rep(i,n){
        rep(j,6005){
            chmax(dp[i+1][j],dp[i][j]);
            if(j<t) chmax(dp[i+1][j+v[i].first], dp[i][j]+v[i].second);
        }
    }
    ll ans = 0;
    rep(i,n){
        rep(j,6005){
            chmax(ans, dp[n][j]);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 260736
def floor_sum(n, m, a, b):
    res = 0
    while True:
        if a >= m:
            res += a//m * n * (n-1) // 2
            a %= m
        if b >= m:
            res += b//m * n
            b %= m
        Y = (a*n+b) // m
        X = Y*m-b
        if Y == 0:
            return res
        res += (n+(-X//a)) * Y
        n, m, a, b = Y, a, m, -X%a

import sys
input = sys.stdin.buffer.readline
t = int(input())
for _ in range(t):
    n, m, a, b = map(int, input().split())
    print(floor_sum(n, m, a, b))

Measured memory_bytes: 70536
#include <stdio.h>

void shuffle(int,int,int,int,int*);

void shuffle(int a,int b,int c,int d,int dice[6])
{
    int box;
    box = dice[a];
    dice[a] = dice[b];
    dice[b] = dice[c];
    dice[c] = dice[d];
    dice[d] = box;
}

int main()
{
    int dice[6];
    char when[100]={};
    for(int i=0;i<6;i++){
        scanf("%d",&dice[i]);
    }
    scanf("%s",when);
    int i = 0,flg = -1,box;
    while(1)
    {
        switch(when[i]){
            case 'W':
                shuffle(5,3,0,2,dice);
                break;
            case 'E':
                shuffle(5,2,0,3,dice);
                break;
            case 'S':
                shuffle(5,1,0,4,dice);
                break;
            case 'N':
                shuffle(4,0,1,5,dice);
                break;
            default:
                flg = 1;
                break;
        }
        if(flg == 1) break;
        i++;
    }
    printf("%d\n",dice[0]);
    return 0;
}




Measured memory_bytes: 2116
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#include "bits/stdc++.h"
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
ll kiri(double a){
	if(a>=0) return (ll)a;
	else return (ll)(a-1);
}
int main(){
	int Q;
	scan(Q);
	int Anum=0;
	ll bias=0;
	ll ftyuo=0;
	set<double> A;
	double tyuo;
	rep(i,Q){
		int q;
		scan(q);
		if(q==1){
			ll a,b;
			scan(a>>b);
			A.insert(a+0.000001*i);
			if(Anum==0){
				tyuo=a+0.000001*i;
				//printf("i:%d Anum:%d tyuo:%llf\n",i,Anum,tyuo);
			}
			else{
				if(tyuo>a+0.000001*i&&Anum%2==1){
					auto itr=A.lower_bound(tyuo);
					itr--;
					//printf("i:%d Anum:%d ftyuo:%lld tyuo:%llf a:%lld b:%lld itr:%llf ",i,Anum,ftyuo,tyuo,a,b,*itr);
					ftyuo+=kiri(fabs((*itr)-tyuo)+0.4);
					//printf("ftyuo:%lld\n",ftyuo);
					tyuo=*itr;
				}
				else if(tyuo<a+0.000001*i&&Anum%2==0){
					auto itr=A.upper_bound(tyuo);
					tyuo=*itr;
				}
				ftyuo+=kiri(fabs(a-tyuo)+0.4);
			}
			bias+=b;
			Anum++;
		}
		else{
			printf("%lld %lld\n",kiri(tyuo+0.4),ftyuo+bias);
		}
	}
	return 0;
}


Measured memory_bytes: 9600
#include <bits/stdc++.h>
#include <math.h>
#include <cmath>

using namespace std;
using ll =long long;
using vi = vector<int>; 
using vvi = vector<vi>; 
using vl = vector<ll>; 
using vvl = vector<vl>; 
using vs = vector<string>;
using vvs = vector<vs>; 
using vc = vector<char>;
using vvc = vector<vc>; 
using vb = vector<bool>;
using vvb = vector<vb>; 

#define rep(i,n) ;for( int i =0; i < n ; i ++)
#define all(a) a.begin(),a.end()
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define f(i,a,b) for(int i=a;i<b;i++)
#define pri(a)  printf("%.14lf\n",a);
#define MOD 1000000007
bool is_int_lround(double x){
  return std::lround(x)==x;
}
ll keta(ll x){
  ll n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}

ll conbi(int n,int m){
  
  cin>>n>>m;
  vector<ll> a(100);
  a[0] =1;
  for(int i=0;i<14;i++){
    a[i+1]=a[i]*(i+1);
  }
  return a[n] /(a[m] *a[n-m]);
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;//繰り返し二乗法
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
ll kaijo(ll x){
  ll z=1;
  if(x==0){
    return 1;
  }
  while(x>0){
    z *=x;
    z %=MOD;
    x--;
  }
  return z;
}
ll yakusu_num(ll n){
  vl yakusu(n+1,1);
  for(ll i=2;i*i<=n;i++){ 
    while(n%i==0){
      n /=i;
      yakusu[i]++;
    }
  }
  if(n!=1)yakusu[n]++;
  ll num=1;
  for(ll i=0;i<=n;i++){
    num*=yakusu[i];
  }
  return num;
}

int H,W;
vs s(50);
vi dv ={-1,0,1,0};vi du={0,-1,0,1};
int cnt=1;
int dfs(int u,int v){
  s[u][v]='.';
  
  rep(i,4){
   
      int nu =u +du[i],nv=v+dv[i];
      if(nu<0||nu>=H||nv<0||nv>=W)continue;
      if(s[nu][nv]=='.')continue;
      cnt ++;
      dfs(nu,nv);
    
  }
  return cnt;

}
int keta_wa(int x){
  int tot=0;
  while(x>0){
    tot +=x%10;
    x/=10;
  }
  return tot;
}

//vc alp ={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
//cout<<""<<endl;
int main(){
  int A,B;cin>>A>>B;if(A%3==0||B%3==0||(A+B)%3==0)cout<<"Possible"<<endl;
  else cout<<"Impossible"<<endl;
  
    
}





Measured memory_bytes: 256
# coding: utf-8
# Your code here!

e1, e2, e3, e4 = map(int, input().split())
if ((e1 == e2) and (e3 == e4)) or ((e1 == e3) and (e2 == e4)) or ((e1 == e4) and (e2 == e3)):
   print("yes")
else:
   print("no")


Measured memory_bytes: 5600
#include<bits/stdc++.h>

using   namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;

#define  all(v)       (v).begin(),(v).end()
#define  rall(v)      (v).rbegin(),(v).rend()
#define  pb           push_back  
#define  eb           emplace_back
#define  mp           make_pair
#define  ff           first
#define  ss           second
#define  pf           push_front
#define  bs           binary_search
#define  lb           lower_bound
#define  ub           upper_bound
#define  umap         unordered_map
#define  uset         unordered_set
#define  dec(x)       fixed<<setprecision(x)
#define  lcm(a,b)    (a*b/__gcd(a,b))

typedef  priority_queue<ll>  pq;
typedef  priority_queue<ll,vector<ll>,greater<ll>> pqmn;
typedef  pair<ll,ll> pll;

const    ll inf=LLONG_MAX;
const    ll mod=1e9+7;
const    ld pi=acos(-1);

vector<ll> arr[1000001];
bool vis[1000001]={false};
void dfs(ll n)
{
    vis[n]=true;
    for(auto i: arr[n]){
        if(!vis[i]){
            dfs(i);
        }
    }
}
                    
void solution()
{ 
    ll n,m;
    cin>>n>>m;
    while(m--){
        ll x,y;
        cin>>x>>y;
        arr[x].pb(y);
        arr[y].pb(x);
    }
    ll cc=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            cc++;
            dfs(i);
        }
    }
    cout<<cc-1;

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll t;
    t=1;
    //cin>>t;
    while(t--){
        solution();
        cout<<"\n";
    }
    return 0;
}


Measured memory_bytes: 31464
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

class Dijkstra {
public:
    struct edge { long long v, dist; };

    struct state {
        long long v, cost;
        bool operator>(const state s) const { return cost > s.cost; }
    };

    const long long INF = (1LL << 60);
    long long N;
    vector< vector<edge> > E;

    Dijkstra(long long n): N(n), E(n) {}

    //有効グラフの時はこっち。u→vに距離dで結ぶ
    void add_directed_edge(long long u, long long v, long long d) {
        E[u].push_back((edge) { v, d });
    }

    //無向グラフの時はこっち。uとvを双方向に距離dで結ぶ
    void add_undirected_edge(long long u, long long v, long long d) {
        E[u].push_back((edge) { v, d });
        E[v].push_back((edge) { u, d });
    }

    //Sを始点として、他の頂点への最短経路を探す
    vector<long long> shortest_path(long long S) {
        vector<long long> dp(E.size(), INF);
        priority_queue<state, vector<state>, greater<state> > q;
        q.push((state) { S, 0 });
        while(!q.empty()) {
            long long v = q.top().v, cost = q.top().cost;
            q.pop();
            if(dp[v] <= cost) continue;
            dp[v] = cost;
            for(int i=0;i < E[v].size() ; i++) {
            long long nv = E[v][i].v, ncost = cost + E[v][i].dist;
            if(dp[nv] > ncost) q.push((state) { nv, ncost });
            }
        }
        return dp;
    }
};


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
    
    ll n,s,t;
    cin>>n>>s>>t;
    s--,t--;
    Dijkstra dij(n);
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        a--,b--;
        dij.add_undirected_edge(a,b,1);
    }
    int now = 0;
    int p = 0;
    vector<ll> d=dij.shortest_path(0);
    for(int i=0;i<n;i++){
        if(now < d[i]){
            now = d[i];
            p=i;
        }
    }
    vector<ll> f=dij.shortest_path(p);
    now=0;
    int q=0;
    for(int i=0;i<n;i++){
        if(now<f[i]){
            now = f[i];
            q=i;
        }
    }
    bool used[n]={};
    for(int i=0;i<n;i++){
        if(now == d[i] + f[i]) used[i]=1;
    }
    vector<ll> sd = dij.shortest_path(s);
    vector<ll> td = dij.shortest_path(t);
    ll ans = -1;
    if(sd[p]==td[p]) ans = max(ans,sd[t]/2);
    if(sd[q]==td[p]) ans = max(ans,sd[t]/2);
    for(int i=0;i<n;i++){
        if(sd[t]%2 && sd[i] < td[i]){
            ans = max(ans, td[i]-1);
        }
        else if(sd[i] < td[i]) ans = max(ans,td[i]-1);
    }
    cout << ans << endl;


}


Measured memory_bytes: 12532
///-BISMILLAHIR RAHMANIR RAHIM-///
#include <bits/stdc++.h>
#include<vector>
using namespace std;
#define pb push_back
#define scn(n) scanf("%lld",&n)
#define pi acos(-1)
#define ll long long
#define llu unsigned long long
#define mod 1000000007
int main()
{
    string w,t;
    cin>>w;
    ll ans=0;
    while(cin>>t)
    {
        if(t=="END_OF_TEXT")
            break;
        for(ll i=0; i<t.size(); i++)
            if(t[i]>='A' && t[i]<='Z')
                t[i] += 'a'-'A';
        if(w==t)
            ans ++;
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 3128
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>


/* 
*    coder :: ATUL_PANDEY_2608
*        >>> INDIA <<<
*/
using namespace std;
using namespace __gnu_pbds;

// #define  part ..
#define pb(a) push_back(a)
#define all(a) a.begin(),a.end() 
#define mod 1000000007
//#define maxx 200006
#define ll long long 
#define quick    ios_base::sync_with_stdio(NULL),cin.tie(0);
#define listll vector< long long > 
#define listi vector< int> 
#define pii   pair<int , int> 
#define pll pair<long long , long long > 
#define minheap priority_queue<long long , vector< long long >, greater<long long > >
#define rep(i,a,b) for(int i=a;i<b;i++)
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll power( ll a, ll n, ll m){
  ll ans = 1;
  while(n){
  if(n&1)
  {
  ans *= a;
  ans%=m;
  }
  a*=a;
  a%=m;
  n/=2;
  }
  return ans ;
} 


template < class T > using oset = tree< T , null_type, less  < T  > , rb_tree_tag , tree_order_statistics_node_update > ;


// end of #define 

// define globals ...
const int maxx = 2e5+26;

//write function from here ...







int Main(){



 ll n;
 cin>>n;
 
 if( n<=1)
 {
	 cout<<0;
	 return 0;
 }
 
 ll temp = power( 9 , n , mod );
 ll temp2 = power(8 , n, mod );
 ll ten = power( 10 , n , mod );
 
 ll ans = 0 ;
 ans = ten ;
 ans+=temp2;
 ans -= ((2*temp) %mod);
 ans+=mod;
 ans%=mod;
 cout<<ans ;
 
 
 
 




return 0;

}






int main(){
 quick;
int t =1; 
//cin>>t;
while(t-- )
 Main();

 return 0;


}


Measured memory_bytes: 3624
sList = list(map(int, input().split()))
cnt5 = 0
cnt7 = 0
ansFlg = True
for i in sList:
    if i == 5:
        if cnt5 == 3:
            ansFlg = False
            break
        cnt5 += 1
        continue
    elif i == 7:
        cnt7 += 1
        if cnt7 == 2:
            ansFlg = False
            break
        continue
    else:
        ansFlg = False
        break
if ansFlg:
    print('YES')
else:
    print('NO')

Measured memory_bytes: 3064
#include<bits/stdc++.h>

using namespace std;

int main(){
    string s;
    cin >> s;
    if(s=="SUN"){
        cout << 7 << endl;
    }else if(s=="MON"){
        cout << 6 << endl;
    }else if(s=="TUE"){
        cout << 5 << endl;
    }else if(s=="WED"){
        cout << 4 << endl;
    }else if(s=="THU"){
        cout << 3 << endl;
    }else if(s=="FRI"){
        cout << 2 << endl;
    }else if(s=="SAT"){
        cout << 1 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

constexpr int INF = 1e9;
constexpr ll INFLL = 1e18;

constexpr int dx[4] = {0, 1, 0, -1};
constexpr int dy[4] = {-1, 0, 1, 0};

int main() {
    ll X, Y; cin >> X >> Y;
    if(X % Y == 0) {
        cout << -1 << endl;
    } else {
        for(ll x = X; x <= INFLL; x += X) {
            if(x % Y != 0) {
                cout << x << endl;
                return 0;
            }
        }
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long long LL;
typedef pair<double, int> li;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

#ifdef DEBUG
    #define cek(x) cout<<x
#else
    #define cek(x) if(false){}
#endif // DEBUG

#define fi first
#define se second
#define INF 1000000000
#define INFLL 1000000000000000000LL
#define EPS 1e-9
#define PI acos(-1.0)
#define pb push_back
#define TC() while(tc--)
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORN(i,n) for(int i=0;i<=n;i++)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define REPN(i,a,b) for(int i=a;i<=b;i++)
#define reset(a,b) memset(a,b,sizeof(a))
#define sc(x) scanf("%d",&x)

ll x,y,x2,y2;
typedef struct{
	ll x,y,r;

}point;

point arr[1010];
double dist[1010][1010];

int main(void){
    #ifdef ccsnoopy
        freopen("D:/Code/in.txt","r",stdin);
    #endif

  	cin >> x >> y >> x2 >> y2;
  	int n;
  	sc(n);
  	
  	FOR(i,n){
  		cin >> arr[i].x;
  		cin >> arr[i].y;
  		cin >> arr[i].r;
  	}

  	FOR(i,n){
  		for(int j = i;j<n;j++){
  			if(i == j){
  				dist[i][j] = 0;
  			}else{
  				dist[j][i] = dist[i][j] = sqrt(pow(arr[i].x - arr[j].x, 2) + pow(arr[i].y - arr[j].y, 2));
  				if(dist[i][j] < arr[i].r + arr[j].r){
  					dist[i][j] = dist[j][i] = 0;
  				}else{
  					dist[i][j] = dist[j][i] = dist[j][i] - arr[i].r - arr[j].r;
  				}
  			}
  		}
  	}

  	FOR(i,n){
  		dist[n][i] = dist[i][n] = sqrt(pow(arr[i].x - x, 2) + pow(arr[i].y - y, 2));
  		if(dist[n][i] < arr[i].r){
  			dist[n][i] = dist[i][n] = 0;
  		}else{
  			dist[i][n] = dist[n][i] = dist[n][i] - arr[i].r;
  		}

  		dist[n+1][i] = dist[i][n+1] = sqrt(pow(arr[i].x - x2, 2) + pow(arr[i].y - y2, 2));
  		if(dist[n+1][i] < arr[i].r){
  			dist[n+1][i] = dist[i][n+1] = 0;
  		}else{
  			dist[i][n+1] = dist[n+1][i] = dist[n+1][i] - arr[i].r;
  		}
  	}

  	dist[n][n+1] = dist[n+1][n] = sqrt(pow(x-x2,2) + pow(y-y2,2));

  	priority_queue< li, vector<li>, greater<li> > pq;
  	pq.push(li(0, n));
  	vector<double> distance(n+2, INFLL); distance[n] = 0;

  	while (!pq.empty()) {                                           
    li front = pq.top(); pq.pop();
    double d = front.first;
    int u = front.second;
    if (d > distance[u]) continue;
    for (int j = 0; j < n + 2; j++) {
      if(u == j)continue;
      if (distance[u] + dist[u][j] < distance[j]) {
        distance[j] = distance[u] + dist[u][j];                 
        pq.push(li(distance[j], j));
  } } }

  // FOR(i,n+2){
  // 	FOR(j,n+2){
  // 		cout << dist[i][j] << " ";
  // 	}cout << endl;
  // }

  	printf("%.10lf\n", distance[n+1]);



    return 0;
}




Measured memory_bytes: 12404
#include<bits/stdc++.h>
using namespace std;
struct res{
    string s;
    int v,id;
}ress[150]; 
bool cmp(res a,res b)
{
    return a.s==b.s?a.v>b.v:a.s<b.s;
}
int n;  
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>ress[i].s>>ress[i].v,ress[i].id=i;
    sort(ress+1,ress+n+1,cmp);
    for(int i=1;i<=n;i++)cout<<ress[i].id<<endl;
    return 0;
}

Measured memory_bytes: 256