akhauriyash/Code-Regression huggingface dataset:
class Combination:
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

q = int(input())
info = [list(map(int, input().split())) for i in range(q)]
MOD = 1000003
comb = Combination(MOD, MOD)

for x, d, n in info:
    if d == 0:
        ans = pow(x, n, MOD)
        print(ans)
        continue

    ans = pow(d, n, MOD)
    x_d = x * pow(d, MOD - 2, MOD) % MOD
    
    # x_d * (x_d + 1) * (x_d + 2) * ... *(x_d + n - 1)
    tmp = comb.factorial(min(x_d + n - 1, MOD)) * pow(comb.factorial(x_d - 1), MOD - 2, MOD)
    ans *= tmp
    print(ans % MOD)


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

ll gcd(ll a, ll b) {
	return (b == 0 ? a : gcd(b, a%b));
}
int main() {
	ll A, B; cin >> A >> B;
	cout << A / gcd(A, B) * B << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define REP(i, b, n) for (Int i = b; i < Int(n); i++)
#define rep(i, n) REP(i, 0, n)
using namespace std;
using Int = long long;
Int inf = 1000000000000000001LL;
using vi = vector<Int>;
using vvi = vector<vi>;
using pii = pair<Int,Int>;
using mapis = unordered_map<Int,string>;
using mapii = unordered_map<Int,Int>;

Int GCD(Int a, Int b){
    if(b==0) return a;
    if(a < b) return GCD(b, a);
    unsigned r;
    while ((r=a%b)) {
        a = b;
        b = r;
    }
    return b;
}

Int LCM(Int a, Int b){
    return a*b/GCD(a,b);
}


int main() {
    Int N,K;
    cin >> N>>K;
    vi H = vi(N);
    rep(i,N){
        H[i] = N;
    }
    int ans =0;
    REP(i,K-1,N){
        ans++;
    }

    cout << ans;
    return 0;
}

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

int main(){
    int n;
    ll s=0;
    cin >> n;
    vector <ll> a(n);

    rep(i,n){
        cin >> a[i];
        s+=a[i]*pow(-1,i);
    }

    vector <ll> ans(n);
    rep(i,n){
        ans[i]=s;
        s=2*a[i]-s;
    }

    rep(i,n){
        cout << ans[i] << endl;
    }
    

    return 0;
}

Measured memory_bytes: 2944
#include <bits/stdc++.h>
using namespace std;
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(false), cout << fixed << setprecision(20);
#define int long long
#define gcd __gcd
#define all(x) (x).begin(), (x).end()
const int INF = 1e18, MOD = 1e9 + 7;
template<class T>
bool chmax(T& a, T b){return (a = max(a, b)) == b;}
template<class T>
bool chmin(T& a, T b){return (a = min(a, b)) == b;}
#define _overload(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(...) _overload(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
#define _rev(i, n) revi(i, n, 0)
#define revi(i, a, b) for(int i = (int)(a - 1); i >= (int)(b); i--)
#define rev(...) _overload(__VA_ARGS__, revi, _rev)(__VA_ARGS__)
#define each(i, n) for(auto&& i: n)
signed main() {
    INCANT;
    int n, m, l, a, b, c, q, s, t;
    int g1[333][333] = {}, g2[333][333] = {};
    cin>>n>>m>>l;
    rep(i, n){
        rep(j, n){
            g1[i][j] = g2[i][j] = INF;
        }
    }
    rep(i, m){
        cin>>a>>b>>c;
        a--, b--;
        g1[a][b] = g1[b][a] = c;
    }
    rep(i, n){
        rep(j, n){
            rep(k, n){
                g1[j][k] = min(g1[j][k], g1[j][i] + g1[i][k]);
            }
        }
    }
    rep(i, n){
        rep(j, n){
            if(g1[i][j] <= l) g2[i][j] = 1;
        }
    }
    rep(i, n){
        rep(j, n){
            rep(k, n){
                g2[j][k] = min(g2[j][k], g2[j][i] + g2[i][k]);
            }
        }
    }
    cin>>q;
    rep(i, q){
        cin>>s>>t;
        s--, t--;
        if(g2[s][t]==INF) cout<<-1<<endl;
        else cout<<g2[s][t] - 1<<endl;
    }
}


Measured memory_bytes: 2304
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>
#include<set>
#include<cstdio>

using namespace std;

#define ll long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define P pair<int, int>

typedef vector<int> vec;
typedef vector<vec> mat;

int main(){
    string s, t;
    cin >> s >> t;
    int ans = 0;
    rep(i, s.size()){
        if(s[i] != t[i]){
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3916
#include<stdio.h>

int main(){

	char str[100];
	char *p,*q;

	//?????§????§?20???????????????????????????
	fgets(str, sizeof(str), stdin);

	p = q = str;
	
	//???????????????????°??????§?§????????????????
	while(*q != '\n'){
		q++;
	}
	//???????°?????????????????????????????????????	
	q=q-1;	
	while(q >= p){
		putchar(*q);
		q--;
	}
	printf("\n");
	
    return 0;
}

Measured memory_bytes: 520
#include <iostream>
#include <string>
using namespace std;

int main() {
	string s, t;
	int n[2];
	string u;
	cin >> s >> t;
	cin >> n[0] >> n[1];
	cin >> u;
	if (s == u) {
		n[0]--;
	} else if (t == u) {
		n[1]--;
	}
	cout << n[0] << " " << n[1] << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,a,one=0,two=0,four=0;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a);
		if(a % 2 == 0){
			if(a % 4 == 0){
				four++;
			}
			else{
				two++;
			}
		}
		else{
			one++;
		}
	}
	if(four == one-1 && two == 0){
		printf("Yes");
	}
	else if(four < one){
		printf("No");
	}
	else{
		printf("Yes");
	}
}

Measured memory_bytes: 256
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::{Bytes, Chars, Usize1};
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::ops::*;

#[derive(Clone, Debug, Default)]
struct Struct;




//#[proconio::fastout]
fn main() {
    input! {
        a: f64,
        b: f64,
        h: f64,
        m: f64,
    }
    let minutes = h*60.0+m;
    let a_angle = minutes/(60.0*12.0) * std::f64::consts::PI * 2.0;
    let b_angle = minutes/60.0 * std::f64::consts::PI * 2.0;
    let angle = a_angle - b_angle;

    let dx = a - b * angle.cos();
    let dy = b * angle.sin();


    println!("{}", (dx*dx+dy*dy).sqrt() );
}



Measured memory_bytes: 2904
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
using namespace std;
int main() {
  
  int N;cin>>N;
  vector<int> vec(N);
  for(int i=0;i<N;i++){
    cin>>vec[i];
  }
  
  
  int ans=0;
  
  for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++){
      ans+=vec[i]*vec[j];
    }
  }
  
  cout<<ans<<endl;
}

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

int main() {
    int n;
    cin >> n;
    priority_queue<double, vector<double>, greater<double>> que;
    for (int i = 0; i < n; i++) {
        double v;
        cin >> v;
        que.push(v);
    }

    while ((int)que.size() > 1) {
        double v1 = que.top(); que.pop();
        double v2 = que.top(); que.pop();
        que.push((v1 + v2) / 2);
    }

    cout << que.top() << endl;
}            

Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<deque>
using namespace std;
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
static const ll maxLL = (ll)1 << 62;
const int mod=1e9+7;

int main(){
    int n;
    cin>>n;
    deque<int> v(0);
    if(n%2==1){
        rep(i,0,n){
            int x;
            cin>>x;
            if(i%2==0)v.push_front(x);
            else v.push_back(x);
        }
    }else{
        rep(i,0,n){
            int x;
            cin>>x;
            if(i%2==1)v.push_front(x);
            else v.push_back(x);
        }
    }
    rep(i,0,v.size()){
        if(i!=v.size()-1)cout<<v[i]<<' ';
        else cout<<v[i]<<endl;
    }
    return 0;
}

Measured memory_bytes: 2944
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sys/time.h>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>

using namespace std;

void solve(int N, vector<int> a, vector<int> b) {
    vector<int> used(N+1, 0);
    for (int i = 0; i < N; i++) {
        used[b[i]] = 1;
    }
    int target = -1;
    for (int i = 1; i < N+1; i++) {
        if (used[i] == 0) {
            target = i;
        }
    }
    if (target == -1) {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No" << std::endl;
        for (int i = 0; i < N-1; i++) {
            std::cout << 1 << ' ';
        }
        std::cout << 1 << std::endl;
        for (int i = 0; i < N; i++) {
            if (i > 0) {
                std::cout << ' ';
            }
            if (a[i] == target) {
                std::cout << 2;
            } else {
                std::cout << 1;
            }
        }
        std::cout << std::endl;
    }
}

int main() {
    int N;

    std::cin >> N;
    vector<int> a(N);
    vector<int> b(N);
    for (int i = 0; i < N; i++) {
        std::cin >> a[i];
    }
    for (int i = 0; i < N; i++) {
        std::cin >> b[i];
    }
    solve(N, a, b);

    return 0;
}



Measured memory_bytes: 4748
n=int(input())
p=list(map(int,input().split()))
count=0
for i in range(n-1):
    if i+1==p[i]:
        p[i],p[i+1]=p[i+1],p[i]
        count+=1
if p[n-1]==n:
    count+=1
print(count)

Measured memory_bytes: 52908
#include <cstdio>
using namespace std;

char map[8][8];
 
void check(void)
{
  for (int i = 0; i < 8; i++){
    for (int j = 0; j < 8; j++){
      if (map[i][j] == '1'){
        if (map[i][j + 1] == '1' && map[i + 1][j] == '1' && map[i + 1][j + 1] == '1'){
          puts("A");
        }
        else if (map[i + 1][j] == '1' && map[i + 2][j] == '1' && map[i + 3][j] == '1'){
          puts("B");
        }
        else if (map[i][j + 1] == '1' && map[i][j + 2] == '1' && map[i][j + 3] == '1'){
          puts("C");
        }
        else if (map[i + 1][j] == '1' && map[i + 1][j - 1] == '1' && map[i + 2][j - 1] == '1'){
          puts("D");
        }
        else if (map[i][j + 1] == '1' && map[i + 1][j + 1] == '1' && map[i + 1][j + 2] == '1'){
          puts("E");
        }
        else if (map[i + 1][j] == '1' && map[i + 1][j + 1] == '1' && map[i + 2][j + 1] == '1'){
          puts("F");
        }
        else if (map[i][j + 1] == '1' && map[i + 1][j] == '1' && map[i + 1][j - 1] == '1'){
          puts("G");
        }
      }
    }
  }
} 
int main()
{
    while (scanf(" %c", &map[0][0]) != EOF){
      for (int i = 1; i < 8; i++){
        scanf(" %c", &map[0][i]);
      }   
      for (int i = 1; i < 8; i++){
        for (int j = 0; j < 8; j++){
          scanf(" %c", &map[i][j]);
        }
      }     
      check();
    }
    return (0);
}

Measured memory_bytes: 948
/*B - String Palindrome*/

#include <bits/stdc++.h>

using namespace std;

int main(){

	int palin = true;
	string subPalin = "";
	string cad;
	string aux;
	int tam;

	cin >> cad;
	
	tam = cad.size();
	aux = cad;
	
	reverse(aux.begin(), aux.end());

	if(aux != cad){
		palin = false;
	}

	for (int i = 0; i < (tam - 1) / 2 ; ++i)
	{
		subPalin += cad[i];
	}

	aux = subPalin;

	reverse(aux.begin(), aux.end());

	if(aux != subPalin){
		palin = false;
	}

	subPalin = "";
	for (int i = ((tam + 3) / 2) - 1; i < tam ; ++i)
	{
		subPalin += cad[i];
	}

	aux = subPalin;

	reverse(aux.begin(), aux.end());

	if(aux != subPalin){
		palin = false;
	}

	if(palin)
		cout << "Yes";
	else
		cout << "No";

	return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int D, G;
	cin >> D >> G;
	vector<int> p(D), c(D);
	for (int i = 0; i < D; ++i) {
		cin >> p[i] >> c[i];
	}
	int mincost = 1 << 30;
	for (int i = 0; i < 1 << D; ++i) {
		int cursolved = 0, curpts = 0;
		for (int j = 0; j < D; ++j) {
			if ((i >> j) & 1) {
				cursolved += p[j];
				curpts += p[j] * 100 * (j + 1);
				curpts += c[j];
			}
		}
		for (int j = D - 1; j >= 0; --j) {
			if ((i >> j) & 1) continue;
			int remprob = p[j];
			while (remprob > 0 && curpts < G) {
				++cursolved;
				--remprob;
				curpts += 100 * (j + 1);
			}
		}
		mincost = min(mincost, cursolved);
	}
	cout << mincost << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <vector>
#include <string>
#include <cmath>
#include <map> 
#include <sstream>
#include <cstdio>
#include <complex>
#include <cstring>
using namespace std;
 
const int MAX= 10000100;

#define loop(i,a,b) for(int i = a ; i < b ; i ++)
#define rep(i,a) loop(i,0,a)
#define all(a) (a).begin(),(a).end()
#define ll long long int
#define gcd(a,b) __gcd(a,b)
#define pb(a) push_back(a)
int GCD(int a, int b) {if(!b) return a; return gcd(b, a%b);}
int lcm(int a, int b) {return a*b / gcd(a, b);}

int main(void){
  int n,all=0;
  cin>>n;
  vector<int> v(n);
  rep(i,n){
    cin>>v[i];
    all += v[i];
  }
  int ave1,ave2;
  ave1 = ave2 = all/n;
  if(all%n!=0)ave2++;
  int c1,c2;
  c1 = c2 = 0;
  //rep(i,n)cout<<v[i]<<endl;
  
  rep(i,n){
    c1 += (v[i] - ave1) * (v[i] - ave1);    
    c2 += (v[i] - ave2) * (v[i] - ave2);
  }

  int ret = min(c1,c2);
  cout<<ret<<endl;
}


Measured memory_bytes: 256
import heapq
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
ans=0
line=[]
heapq.heappush(line,-A[0])
for i in range(1,N):
    ans-=heapq.heappop(line)
    heapq.heappush(line,-A[i])
    heapq.heappush(line,-A[i])
print(ans)

Measured memory_bytes: 31864
import sys
input = sys.stdin.readline
n, m, k = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]
B = [list(map(int,input().split())) for i in range(k)]
# print(A)
# print(B)
for i in range(m):
    for j in range(2):
        A[i][j] -= 1
for i in range(k):
    for j in range(2):
        B[i][j] -= 1
# print(A)
# print(B)
 
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
 
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def size(self, x):
        return -self.parents[self.find(x)]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def n_cc(self):  # 連結成分の数
        A = [i for i in self.parents if i < 0]
        return len(A)
 
U = UnionFind(n)
for i in range(m):
    a = A[i][0]
    b = A[i][1]
    U.union(a, b)
C = [0] * n
 
for i in range(m):
    a = A[i][0]
    b = A[i][1]
    C[a] -= 1
    C[b] -= 1
for i in range(k):
    a = B[i][0]
    b = B[i][1]
    if U.find(a) == U.find(b):
        C[a] -= 1
        C[b] -= 1
# print(C)
ANS = []
for i in range(n):
    ANS.append(U.size(i) + C[i] - 1)
print(" ".join([str(i) for i in ANS]))

Measured memory_bytes: 118108
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

int dig(ll a){
    int ret = 0;
    while(a > 0){
        ret++;
        a /= 10;
    }

    return ret;
}

int top(ll a){
    string s = to_string(a);
    return (int)(s[0] - '0');
}

int main(){
    int N;
    cin >> N;
    int nl = top(N);
    int nr = N % 10;
    int digN = dig(N);

    ll pow[10];
    pow[0] = 1;
    for(int i = 1; i < 10; i++){
        pow[i] = pow[i - 1] * 10;
    }

    ll ans = 0;
    for(int i = 1; i <= N; i++){
        int ar = i % 10;
        int al = top(i);

        //cout << i << " " << al << " " << ar << endl;

        if(ar == 0) continue;

        for(int j = 1; j <= digN; j++){
            ll b = ar * pow[j - 1] + al;
            if(j == 1) b = ar;
            //printf("i = %d, j = %d, b = %d\n", i, j, b);
            if(j == 1 && al != ar) continue;

            if(j == 1 || j == 2){
                if(b <= N){
                    ans++;
                }
            }
            else if(j == digN){
                if(ar < nl){
                    ans += pow[j - 2];
                    //ans += max(0LL, (N - b) / 10 + 1);
                }
                else if(ar == nl){
                    if(al <= nr){
                        ans += (N % pow[digN - 1]) / 10 + 1;
                    } else {
                        ans += (N % pow[digN - 1]) / 10;
                    }
                }
            }
            else {
                ans += pow[j - 2];
            }
        }


        //cout << i << " " << ans << endl << endl;
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <stack>
#include <cstdlib>
using namespace std;

int main() {
    string in;
    int l,r;
    stack<int> st;
    while(cin>>in){
        if (in == "+") {
            r = st.top();
            st.pop();
            l = st.top();
            st.pop();
            st.push(l+r);
        } else if (in == "-") {
            r = st.top();
            st.pop();
            l = st.top();
            st.pop();
            st.push(l-r);
        } else if (in == "*") {
            r = st.top();
            st.pop();
            l = st.top();
            st.pop();
            st.push(l*r);
        } else {
            st.push(atoi(in.c_str()));
        }
    }
    cout<<st.top()<<endl;
    return 0;
}


Measured memory_bytes: 3232
/*
 Author: nilesh8757
 */
#include<bits/stdc++.h>
 using namespace std;

#define FIO                     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mod                     1000000007
#define eps                     1e-9
#define setbits                 __builtin_popcount
#define gcd                     __gcd
#define rep(i,a,b)              for(int i=a;i<=b;i++)
#define repr(i,b,a)             for(int i=b;i>=a;i--)
#define forn(i,n)               for(int i=0;i<n;i++)
#define all(a)                  a.begin(), a.end()
#define in(a,b)                 ( (b).find(a) != (b).end())
#define pb                      push_back
#define fill(a,v)               memset(a, v, sizeof a)
#define endl                    "\n"
#define ff                      first
#define ss                      second
#define mp                      make_pair
#define minin(a)                *min_element (all(a))
#define maxin(a)                *max_element(all(a))
#define asort(c)                sort(all(c))
#define dsort(c)                sort(all(c), greater<int>()) 
#define PI                      3.14159265358979323846
#define int                     long long
typedef  vector<int>                 vi;
typedef  pair<int, int>              ii;
typedef  vector<ii>                 vii;
typedef  set<int>                    si;
typedef  map<int, int>              mii;
typedef  long double                 ld;


clock_t time_p=clock();
void timer()
{
    time_p=clock()-time_p;
    cerr<<"Execution Time: "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}

int32_t main()
{
  FIO

  int n,x,dis,g=0,loc;
  cin>>n>>x;
  forn(i,n)
  {
  	cin>>loc;
  	g=gcd(g,abs(loc-x));
  }
  cout<<g;
  timer();
  return 0;
}  

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>

using namespace std;

int main(){
	int N,a,b,ans=100;
	int x=0,y=0,z=0;
	
	cin >> N >> a >> b;
	
	vector<int> v(N);
	
	for(int i=0;i<N;i++){
		cin >> v[i];
	}
	
	for(int i=0;i<N;i++){
		if(a >= v[i])x++; 
		else if(v[i] > a && b >= v[i])y++;
		else if(v[i] > b)z++;
	}
	
	if(x <= ans)ans=x;
	if(y <= ans)ans=y;
	if(z <= ans)ans=z;
	
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <list>

using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
typedef long long ll;

int main() {
    int n;
    int t[100100], x[100100], y[100100];
    cin >> n;
    bool flag = true;
    rep(i, n) cin >> t[i+1] >> x[i+1] >> y[i+1];
    rep(i, n) {
        int d = abs(x[i+1] - x[i]) + abs(y[i+1] - y[i]);
        int dt = t[i+1] - t[i];
        if(d > dt or d%2 != dt%2) {
            flag = false;
            break;
        }
    }

    if(flag) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 1408
N, M = map(int, input().split())
# INF = 10 ** 6
MOD = 10 ** 9 + 7

dp = [0] * (N + 1)
broken = [False] * (N + 1)

for i in range(M):
    broken[int(input())] = True

dp[0] = 1
for i in range(N + 1):
    if broken[i]:
        continue
    if i - 2 >= 0 and not broken[i - 2]:
        dp[i] += dp[i - 2] % MOD
    if i - 1 >= 0 and not broken[i - 1]:
        dp[i] += dp[i - 1] % MOD
# print(dp[:10])
print(dp[N] % MOD)


Measured memory_bytes: 7756
l=[list(map(int,input().split())) for i in range(3)]
n=int(input())
s=set()
for i in range(n):
    s.add(int(input()))
ans="No"
for i in range(3):
    if l[i][0] in s and l[i][1] in s and l[i][2] in s:
        ans="Yes"
    if l[0][i] in s and l[1][i] in s and l[2][i] in s:
        ans="Yes"
if l[0][0] in s and l[1][1] in s and l[2][2] in s:
        ans="Yes"
if l[0][2] in s and l[1][1] in s and l[2][0] in s:
        ans="Yes"
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include<math.h>
#include <vector>
#include <numeric>

using namespace std;

int main() {

    int H, W;
    cin >> H >> W;

    vector< vector<string> > map(H, vector<string>(W));

    for (int i = 0; i < H; ++i) {
        string S;
        cin >> S;
        for (int j = 0; j < W; ++j) {
            map[i][j] = S[j];
        }
    }

    // row が全部 . の場合は消す
    for (int i = 0; i < H; ++i) {
        bool isFind = false;
        for (int j = 0; j < W; ++j) {
            if (map[i][j] == "#") {
                isFind = true;
            }
        }

        if (isFind) {
            continue;
        }

        // delete row
        map.erase(map.begin() + i);
        --H;
        --i;
    }



    // column が全部 . の場合は消す
    for (int i = 0; i < W; ++i) {


        bool isFind = false;
        for (int j = 0; j < H; ++j) {
            if (map[j][i] == "#") {
                isFind = true;
            }
        }

        if (isFind) {
            continue;
        }

        // delete column
        for (int j = 0; j < H; ++j) {
            map[j].erase(map[j].begin() + i);
        }
        --W;
        --i;
    }

    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cout << map[i][j];
        }
        cout << endl;
    }

    return 0;
}

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reps(i,s,n) for(int (i)=(s);(i)<(n);(i)++)
#define repr(i,n) for(int (i)=(n)-1;(i)>=0;(i)--)
#define forin(x,n) for(auto& (x) : n)
#define all(v) (v).begin(),(v).end()
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define mp make_pair
#define pb push_back
#define MOD 1000000007
#define inf 1000000000
#define llinf 1000000000000000
#define MAX 1000000


typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int,int> pint;
typedef pair<ll,ll> pll;
typedef vector<pint> vpint;
typedef pair<int,pint> P;

int main(){
    int n;
    cin>>n;
    vector< pair< pair< string,int >,int > > pp(n);
    //vector<pair<string,int>> pp(n);
    rep(i,n){
        string x;
        int y;
        cin>>x>>y;
        pp[i]=mp(mp(x,-y),i);
        //pp[i]=mp(x,-y);
    }
    sort(all(pp));
    //reverse(all(pp));
    rep(i,n){
        //cout<<pp[i].first.first<<pp[i].first.second<<endl;
        cout<<pp[i].second+1<<endl;
    }
}

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

using namespace std;

using ll = long long;

#define rep(i, a, n) for (int i = (int)(a); i < (int)(n); i++)

ll mod_pow(ll x, ll n, ll mod){
    ll res = 1;
    while(n>0){
        if(n&1) res = res *x%mod;
        x = x*x%mod;
        n>>=1;
    }
    return res;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n; string s; cin >> n >> s;
    ll x = 0ll;
    ll y = 0ll;
    ll mod = 0;
    rep(i,0,n){
        if(s[i]=='1'){
            mod++;
        }
    }
    rep(i,0,n){
        if(s[i]=='1'){
            x += mod_pow(2,(n-i-1),mod+1);
            if(mod-1>0){
                y += mod_pow(2,(n-i-1),mod-1);
                y %= (mod-1ll);
            }
            x %= (mod+1ll);
        }
    }
    rep(i,0,n){
        ll ans = 1;
        ll p;
        if(mod-1==0 && s[i]=='1'){
            cout << 0 << endl;
            continue;
        }
        if(s[i]=='1'){
            p = y;
            p -= mod_pow(2,n-i-1,mod-1);
            p += 2*(mod-1);
            p %= (mod-1);
        }
        else{
            p = x;
            p += mod_pow(2,n-i-1,mod+1);
            p %= (mod+1);
        }
        while(p>0){
            ll mod1 = 0ll;
            for(ll j=1; j<=p; j *= 2ll){
                if(p & j){
                    mod1++;
                }
            }
            p %= mod1;
            ans++;
        }
        cout << ans << endl;
    }
}

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

typedef long long ll;
const int N = 1e5;
ll arr[N+100];
ll gcd(ll a,ll b)
{
	if(a%b==0)return b;
	return gcd(b,a%b);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	ll m;
	cin >> n >> m;
	for(int i=1;i<=n;i++)cin >> arr[i];
	ll lcm = arr[1];
	for(int i=2;i<=n;i++){
		ll g = gcd(lcm,arr[i]);
		lcm = min((lcm*arr[i])/g,2*m+2);
	}
	if(lcm>2*m){
		cout << "0\n";
	}
	else{
		bool f = true;
		sort(arr+1,arr+n+1);
		for(ll i=2;i*i<=lcm;i+=2){
			if(lcm%i==0){
				ll tmp = lcm/i;
				if(binary_search(arr+1,arr+n+1,tmp))f = false;
				if(tmp%i==0)if(binary_search(arr+1,arr+n+1,i)) f = false;
			}
		}
		if(!f){
			cout << "0\n";
		}
		else{
			ll cnt = (2*m)/lcm;
			cout << (cnt+1)/2 << "\n";
		}
	}
}


Measured memory_bytes: 1024
/**************************************************************************
Coded by: Saba Karimi(_VINTAGE)
Institution: AIT PUNE
***************************************************************************/
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back 
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define ld long double
#define int long long int 
/**************************************************************************/
signed main()
{
    fast;
    int a,p;
    cin>>a>>p;
    p = p+a*3;
    cout<<p/2;
}   

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

using namespace std;

int dp[100005];
int a[100005];
int wb(int x, int y)
{
    int k=x-y;
    if(k>=0) return k;
    else return -k;
}
int main()
{
    int N;
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        cin>>a[i];
    }
    dp[1]=0;
    dp[2]=wb(a[1],a[2]);
    for(int i=3;i<=N;i++)
    {
        if(dp[i-1]+wb(a[i],a[i-1])<dp[i-2]+wb(a[i],a[i-2])) dp[i]=dp[i-1]+wb(a[i],a[i-1]);
        else dp[i]=dp[i-2]+wb(a[i],a[i-2]);
    }
    cout<<dp[N];
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000000;
int n,f[maxn + 10];
vector<int> g[maxn + 10];
void dfs(int x, int fa) {
    bool isb = 0;
    for (int i = 0; i < (int)g[x].size(); ++i) {
        int e = g[x][i];
        if (e != fa) {
            dfs(e, x); f[x] += f[e];
            if (!f[e]) {
                if (!isb) isb = 1;
                else ++f[x];
            }
        }
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; ++i) {
        int l, r; scanf("%d%d", &l, &r); ++l; ++r;
        g[l].push_back(r); g[r].push_back(l);
    }
    for (int i = 1; i <= n; ++i)
        if ((int)g[i].size() > 2) {
            dfs(i, 0);
            printf("%d", f[i]); return 0;
        }
    printf("1");
}


Measured memory_bytes: 32128
import sys

class Node:
    __slots__ = ['key', 'left', 'right']
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

root = None

def insert(key):
    global root
    x, y = root, None
    while x is not None: x, y = x.left if key < x.key else x.right, x
    if y is None: root = Node(key)
    elif key < y.key: y.left = Node(key)
    else: y.right = Node(key)

def find(target):
    result = root
    while result and target != result.key:
        result = result.left if target < result.key else result.right
    return result is None

def delete(target):
    def remove_node(p, c, a):
        if p.left == c: p.left = a
        else: p.right = a
    p, c = None, root
    while c.key != target: p, c = c, c.left if target < c.key else c.right
    if c.left is None:
        remove_node(p, c, c.right)
    elif c.right is None:
        remove_node(p, c, c.left)
    elif c.right.left is None:
        c.right.left = c.left
        remove_node(p, c, c.right)
    else:
        g = c.right
        while g.left.left is not None: g = g.left
        c.key = g.left.key
        g.left = g.left.right

def inorder(node):
    return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
def preorder(node):
    return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''

input()
for e in sys.stdin:
    if e[0] == 'i': insert(int(e[7:]))
    elif e[0] == 'd': delete(int(e[7:]))
    elif e[0] == 'f': print(['yes','no'][find(int(e[5:]))])
    else: print(inorder(root)); print(preorder(root))


Measured memory_bytes: 56372
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <math.h>
#include <algorithm>

using namespace std;

class Edge
{
public:
  int dst, d;
  Edge(int _dst, int _d)
  : dst(_dst), d(_d)
  {}
};
class Node
{
public:
  vector<Edge> E;
};

int main()
{
  int N;
  cin >> N;
  vector<Node> Nodes(N);
  vector<int> color(N, -1);
  for (int i =0;i<N-1;i++) {
    int a, b, d;
    cin >> a >> b >> d;
    Nodes[a-1].E.push_back(Edge(b-1, d));
    Nodes[b-1].E.push_back(Edge(a-1, d));
  }
  queue<int> q;
  q.push(0);
  color[0] = 0;
  while (!q.empty()) {
    int index = q.front();
    Node& cur = Nodes[index];
    q.pop();
    for (int i = 0; i < cur.E.size(); i++) {
      if (color[cur.E[i].dst] == -1) {
        color[cur.E[i].dst] = cur.E[i].d % 2 == 0 ? color[index] : 1 - color[index];
        q.push(cur.E[i].dst);
      }
    }
  }
  for (int i = 0; i < N; i++) {
    cout << color[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 8704
#include <iostream>
#include <numeric>
#include <cmath>
#include <limits>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;

using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
ll Max(ll(a), ll(b), ll(c)) {
	return max(max(a, b), c);
}
ll Min(ll(a), ll(b), ll(c)) {
	return min(min(a, b), c);
}
ll mod = 1e9 + 7;
int main() {
	ll N;
	cin >> N;
	ll a = 1, b = 2, c = 1;
	rep(i, N) {
		a *= 10;
		a %= mod;
		b *= 9;
		b %= mod;
		c *= 8;
		c %= mod;
	}
	cout << (a - b + c + 10 * mod) % mod << endl;

}

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

char A[ 110 ][ 110 ];
bool h[ 110 ];
bool w[ 110 ];

int main()
{
int i;
int j;
int H;
int W;

	ios::sync_with_stdio( false );
	cin.tie( 0 );

	cin >> H;
	cin >> W;

	for( i = 0; i < H; i++ )
	{
		cin >> A[ i ];
		for( j = 0; j < W; j++ )
		{
			if( A[ i ][ j ] == '#' )
			{
				h[ i ] = true;
				w[ j ] = true;
			}
		}
	}

	for( i = 0; i < H; i++ )
	{
		if( ! h[ i ] ) continue;

		for( j = 0; j < W; j++ )
		{
			if( w[ j ] ) cout << A[ i ][ j ];
		}

		cout << endl;
	}

	return 0;
}






Measured memory_bytes: 256
open System
open System.Collections.Generic

[<AutoOpen>]
module Cin =
    let read f = stdin.ReadLine() |> f
    let reada f = stdin.ReadLine().Split() |> Array.map f
    let readChars() = read string |> Seq.toArray
    let readInts() = readChars() |> Array.map (fun x -> Convert.ToInt32(x.ToString()))

[<AutoOpen>]
module Cout =
    let writer = new IO.StreamWriter(new IO.BufferedStream(Console.OpenStandardOutput()))
    let print (s: string) = writer.Write s
    let println (s: string) = writer.WriteLine s
    let inline puts (s: ^a) = string s |> println

let main() =
    let N = read int
    let A = reada int64 |> Array.sort
    let B = reada int64 |> Array.sort
    let C = reada int64 |> Array.sort

    let lower (arr: int64 array) n a =
        let mutable (ok, ng) = (n, -1)
        while abs (ok - ng) > 1 do
            let mid = (ok + ng) / 2
            if a <= arr.[mid] then ok <- mid else ng <- mid
        ok

    let upper (arr: int64 array) n a =
        let mutable (ok, ng) = (n, -1)
        while abs (ok - ng) > 1 do
            let mid = (ok + ng) / 2
            if a < arr.[mid] then ok <- mid else ng <- mid
        ok

    let mutable ans = 0L
    for i in 0 .. N - 1 do
        let b = B.[i]
        let oka = lower A N b
        let okc = upper C N b

        let elma = int64 oka
        let elmc = N - okc |> int64
        ans <- ans + (elma * elmc)

    puts ans
    ()

main()
writer.Close()


Measured memory_bytes: 38560
# C
N = int(input())

red_list = []
blue_list = []

for _ in range(N):
    x, y = map(int, input().split())
    red_list.append([x, y])

for _ in range(N):
    x, y = map(int, input().split())
    blue_list.append([x, y])
    
GR = dict()
GB = dict()

for i in range(N):
    GR[i+1] = [0, [], 0]
    GB[i+1] = [0, [], 0]

for i in range(N):
    for j in range(N):
        if red_list[i][0] < blue_list[j][0] and red_list[i][1] < blue_list[j][1]:
            GR[i+1][1].append(j+1)
            GB[j+1][1].append(i+1)
            
def find_path(GR_, GB_, N):
    GR = GR_.copy()
    GB = GB_.copy()

    done_red = [0]*(N+1)
    can_red = [0]*(N+1)
    done_blue = [0]*(N+1)

    # start from RED
    for i in range(1, N+1): 
        if GR[i][0] == 0:
            can_red[i] = 1
        GR[i][2] = -1
        GB[i][2] = -1

    while True:

        go_flg = 0
        for i in range(1, N+1):
            if can_red[i] == 1 and done_red[i] == 0:
                go_flg = 1

        if go_flg == 0:
            return []

        for i in range(1, N+1): 
            if can_red[i] == 1 and done_red[i] == 0:
                done_red[i] = 1
                for j in GR[i][1]:
                    if done_blue[j] == 0:
                        GB[j][2] = i
                        done_blue[j] = 1
                        if GB[j][0] != 0:
                            can_red[GB[j][0]] = 1
                            GR[GB[j][0]][2] = j
                        else:
                            # found
                            res_list = [j, i]
                            while GR[res_list[-1]][2] > 0:
                                j = GR[res_list[-1]][2]
                                i = GB[j][2]
                                res_list.append(j)
                                res_list.append(i)
                            return res_list
                        
# set initial path
res = 0
for i in range(1, N+1):
    for j in GR[i][1]:
        if GB[j][0] == 0:
            GR[i][0] = j
            GB[j][0] = i
            res += 1
            break

while True:
    new_path = find_path(GR, GB, N)
    if len(new_path) == 0:
        break
    else:
        for l in range(len(new_path) // 2):
            j, i = new_path[2*l], new_path[2*l+1]
            GB[j][0] = i
            GR[i][0] = j
        res += 1

print(res)
            

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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;


#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};


int main()
{
    int n;
    cin>>n;
    int cnt[4];
    string s[4] = {"AC","WA","TLE","RE"};
    for (int i = 0; i < 4; i++)
    {
        cnt[i]=0;
    }
    
    for (int i = 0; i < n; i++)
    {
        string ss;
        cin>>ss;
        for (int j = 0; j < 4; j++)
        {
            if(ss==s[j])
            {
                cnt[j]++;
                break;
            }
        }
    }
    for (int i = 0; i < 4; i++)
    {
        cout<<s[i]<<" x "<<cnt[i]<<endl;
    }
    
    
    return 0;
}

Measured memory_bytes: 3624
/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
  	int dp[];
  	Main(int n){
      dp = new int[n];
      for(int i = 0; i < n; i++) dp[i] = -1;
    }
	public static void main (String[] args) throws java.lang.Exception
	{
      	FastReader s = new FastReader();
		int  n = s.nextInt();
		int arr[] = new int[n];
		for(int i=0;i<n;i++)
		arr[i]= s.nextInt();
		Main ob = new Main(n);
		int ans = ob.getCost(n-1,arr);
		System.out.println(ans);
	}
	int getCost(int n, int arr[]){
      	if (dp[n]!=-1) return dp[n];
		if(n==0) { 
          dp[0] = 0;
          return dp[0];
        }
		if(n==1) {
          dp[1] = Math.abs(arr[1]-arr[0]);
          return Math.abs(arr[1]-arr[0]);
        }
      	dp[n]=Math.min(Math.abs(arr[n]-arr[n-1])+getCost(n-1,arr),Math.abs(arr[n]-arr[n-2])+getCost(n-2,arr));
		return dp[n];
	}
  static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
}


Measured memory_bytes: 49012
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#define REP(i,n) for(int i = 0;i < (n);i++)
#define pb push_back
using namespace std;
const int INF = 1e9;
typedef long long ll;

int main(){
  int a,b;
  cin >> a >> b;
  if((a*b)%2 == 0){
    cout << "Even" << endl;
  }
  else
    cout << "Odd" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const ll mod = 1000000007;
const ll INF = mod * mod;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
typedef vector<int> vec;
typedef vector<string> svec;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//#define int long long

void solve() {
    map<int, int> mp;
    rep(i, 3) {
        int a, b; cin >> a >> b;
        mp[a] ++; mp[b] ++;
    }
    if(mp[1] == 3 || mp[2] == 3 || mp[3] == 3 || mp[4] == 3) {
        cout << "NO" << endl;
        return;
    }
    cout << "YES" << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//init();
	solve();
	//cout << "finish" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef int lli;
const lli N=2e5+5;
lli a[N], ans[N];
int length;
vector<lli> v[N], dp(N);

void dfs(lli x, lli par)
{
    lli flag=0,ind,val;
    auto it=dp.begin();
    
    if(length==0)
    {
        dp[0]=a[x];
        length=1;
    }
    else
    {
        it=lower_bound(dp.begin(), dp.begin()+length, a[x]);
        
        if(it==dp.begin()+length)
        {
            dp[length]=a[x];
            length++;
        }
        else
        {
            flag=1;
            val=*it;
            *it=a[x];
        }
    }
    ans[x]=length;
    
    for(auto j : v[x])
    {
        if(j==par) continue;
        
        dfs(j, x);
    }
    
    if(flag) *it=val;
    else     length--;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    lli n;
    cin>>n;
    lli i,x,y;
    
    for(i=1;i<=n;i++) cin>>a[i];
    
    for(i=0;i<n-1;i++)
    {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    
    dfs(1,1);
    
    for(i=1;i<=n;i++) cout<<ans[i]<<endl;
    return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> vec(N);
  vec.at(0) = -1;
  for (int i = 1; i < N; i++) {
    cin >> vec.at(i);
  }
  vector<vector<int>> vec2(N);
  for (int i = 1; i < N; i++) {
    int parent = vec.at(i) - 1;
    vec2.at(parent).push_back(i);
  }

  for (int i = 0; i < N; i++) {
    cout << vec2.at(i).size() << endl;
  }
}

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

bool check(string s) {
    int l = s.length();
    if(l%2==1) return false;
    return(s.substr(0,l/2)==s.substr(l/2)); //s.substr(0,l/2)>>>sの0番目からl/2個抽出
}

int main() {
    string s;
    cin >> s;
    int l = s.length();
    for (int i = l-1;; i--) 
    {
        if(check(s.substr(0,i))) {
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define MOD (int) (1e9+7)
#define INF (int) 2e9
#define LLINF (ll) 2e18

int main(){
    int n;
    cin >> n;
    int a[n];
    map<int, int>m;
    rep(i, n){
        cin >> a[i];
        m[a[i]]++;
    }
    
    ll ans = 0;
    for(auto mi : m){
        ans += (ll)mi.second*(mi.second-1)/2;
    }

    rep(i, n){
        int tmp = m[a[i]] -1;
        ans -=  tmp;
        cout << ans << endl;
        ans += tmp;
    }
    return 0;
}

Measured memory_bytes: 9216
N = int(input())
W1 = input()
past = set()
past.add(W1)
last = W1[-1]
ans = 'Yes'
for _ in range(N - 1):
    W = input()
    if W in past or not W.startswith(last):
        ans = 'No'
    else:
        past.add(W)
        last = W[-1]
print(ans)

Measured memory_bytes: 3060
#include<iostream>
#include<string>
using namespace std;

int main(){
int a;
string s, t, ans;
cin >> s >> t;
a = s.size();
ans = "Yes";
for(int i = 0;i < a;i++){
if(s.at(i) != t.at(i)){
ans = "No";
break;
}
}
cout << ans;
}



Measured memory_bytes: 3568
package main

// Solution for https://atcoder.jp/contests/abc174/tasks/abc174_b

import (
	"bufio"
	"fmt"
	"io"
	"os"
)

type contest struct {
	in  io.Reader
	out io.Writer
}

func (con *contest) Scan(a ...interface{}) (int, error) {
	return fmt.Fscan(con.in, a...)
}
func (con *contest) Scanln(a ...interface{}) (int, error) {
	return fmt.Fscanln(con.in, a...)
}
func (con *contest) Scanf(f string, a ...interface{}) (int, error) {
	return fmt.Fscanf(con.in, f, a...)
}
func (con *contest) Print(a ...interface{}) (int, error) {
	return fmt.Fprint(con.out, a...)
}
func (con *contest) Println(a ...interface{}) (int, error) {
	return fmt.Fprintln(con.out, a...)
}
func (con *contest) Printf(f string, a ...interface{}) (int, error) {
	return fmt.Fprintf(con.out, f, a...)
}
func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()
	con := &contest{in: in, out: out}
	con.main()
}

func (con *contest) main() error {
	var n, d int
	con.Scan(&n, &d)
	c := 0
	for i := 0; i < n; i++ {
		var x, y int
		con.Scan(&x, &y)
		if x*x+y*y <= d*d {
			c++
		}
	}
	con.Println(c)
	return nil
}


Measured memory_bytes: 6032
#include <iostream>

int main()
{
	int d, n;
	std::cin >> d >> n;

	int d0[100];
	int d1[100];
	int d2[100];

	int *dX[3] = { d0, d1, d2 };

	// 100で割り切れない値を代入しておく
	for ( int i = 0; i < 100; i++ )
	{
		d0[i] = i + 1;
	}
	d0[99] = 101;

	// 100で1度だけ割り切れる値を代入しておく
	for ( int i = 0; i < 100; i++ )
	{
		d1[i] = d0[i] * 100;
	}

	// 100で2度割り切れる値を代入しておく
	for ( int i = 0; i < 100; i++ )
	{
		d2[i] = d1[i] * 100;
	}

	std::cout << dX[d][n - 1] << std::endl;

	return ( 0 );
}


Measured memory_bytes: 380
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

typedef long long ll;

ll f(ll n, ll x) {
        if (n >= 0)
                return n / x + 1;
        else
                return 0;
}

int main() {
        ll a, b, x;
        cin >> a >> b >> x;
        cout << f(b, x) - f(a - 1, x) << endl;
        return 0;
}

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

using namespace std;

#define MOD 1000000007
#define N 100005
#define pb push_back
#define ll long long

vector <int> g[N];
ll dp[N][2];

void dfs(int node, int par){
	dp[node][0] = 1;
	dp[node][1] = 1;
	for(auto it : g[node]){
		if(it != par){
			dfs(it, node);
			dp[node][0] = (dp[node][0] * (dp[it][0] + dp[it][1]) % MOD) % MOD;
			dp[node][1] = (dp[node][1] * dp[it][0]) % MOD;
		}
	}
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n; cin>>n;
	int m, x, y, i;
	m = n-1;
	while(m--){
		cin>>x>>y;
		g[x].pb(y);
		g[y].pb(x);
	}
	dfs(1, 0);
	int ans = (dp[1][0] + dp[1][1]) % MOD;
	cout<<ans;
	return 0;
}


Measured memory_bytes: 14208