akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<cstdlib>
#include<vector>
const int N=1e5+3;
int n,a[N],rt,s,f[N];
std::vector<int>g[N];
void Dfs(int u,int fa){
	int v;
	for(int i=0;i<g[u].size();i++)if((v=g[u][i])!=fa)
	  a[u]-=a[v],Dfs(v,u);
}
void Dfs1(int u,int fa){
	int v,mx=0;
	for(int i=0;i<g[u].size();i++)if((v=g[u][i])!=fa)
	  Dfs1(v,u),f[u]+=f[v],mx=std::max(mx,f[v]);
	if(g[u].size()>1&&a[u]>0)exit(0*puts("NO"));
	if(g[u].size()>1&&a[u]<0){
	  if(std::min(f[u]-mx,f[u]/2)<-a[u])exit(0*puts("NO"));
	  f[u]+=a[u]*2;
	  a[fa]-=a[u],a[u]=0;
	}
	if(g[u].size()==1)f[u]=a[u];
}
int main(){
	int u,v;
	scanf("%d",&n);
	for(u=1;u<=n;u++)scanf("%d",a+u);
	for(int i=1;i<n;i++)
	  scanf("%d%d",&u,&v),
	  g[u].push_back(v),g[v].push_back(u);
	if(n==2)return 0*puts(a[1]==a[2]?"YES":"NO");
	for(u=1;u<=n;u++)if(g[u].size()>1)rt=u;
	a[0]-=a[rt],Dfs(rt,0);
	Dfs1(rt,0);
	return 0*puts(a[0]?"NO":"YES");
}

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

#define INF 1000000
typedef long long ll;
ll minCost(ll n, ll *arr, ll *dp)
{
    if(n < 1)
        return INF;
    if(n == 1)
        return 0;
    if(dp[n] != -1)
        return dp[n];
    ll ans1 = abs(arr[n]-arr[n-1]) + minCost(n-1, arr, dp);
    ll ans2 = INF;
    if(n >= 3)
         ans2 = abs(arr[n]-arr[n-2]) + minCost(n-2, arr, dp);
    dp[n] = min(ans1, ans2);
    return dp[n];
}

int main()
{
    ll n;
    cin>>n;
    ll arr[n+1];
    for(ll i=1; i<=n; i++)
        cin>>arr[i];
    ll *dp =  new ll[n+1];
    for(ll i=0; i<=n; i++)
        dp[i] = -1; 
    cout<<minCost(n, arr, dp);
}

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

template <typename T> void chmin(T &x,const T &y)
{
	if(x>y)x=y;
}
typedef long long s64;

int main()
{
	//freopen("1.in","r",stdin);
	s64 c25,c5,c1,c2,n;
	cin>>c25>>c5>>c1>>c2>>n;
	chmin(c5,c25*2);
	chmin(c1,c5*2);
	chmin(c2,c1*2);
	cout<<(n/2)*c2+(n%2)*c1;	
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cstring>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <regex>
#include <vector>

#define fix(n)          cout<<fixed<<setprecision(n)
#define rep(i,n)        for (int i = 0; i < (n); ++i)
#define sort(a)         sort((a).begin(), (a).end())
#define uniq(a)         sort(a);(a).erase(unique((a).begin(), (a).end()), (a).end())
#define reverse(a)      reverse((a).begin(), (a).end())
#define ctos(c)         string(1, (c))
#define out(d)          cout << (d)
#define outl(d)         std::cout<<(d)<<"\n"
#define YES()           cout << "YES" << endl
#define NO()            cout << "NO" << endl
#define Yes()           cout << "Yes" << endl
#define No()            cout << "No" << endl
#define ceil(x, y)      ((x + y - 1) / (y))
#define debug(x)        cerr << #x << ": " << (x) << '\n'
#define debug2(x, y)    cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v)          for (size_t _ = 0; _ < v.size(); ++_){ cerr << #v << "[" << _ << "] : " << v[_] << '\n'; }

using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;

const ll MOD = 1000000007; // 10^9 + 7
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

void solve() {
  int n; cin >> n;
  deque<ll> deq;
  rep(i, n) {
    ll a; cin >> a;
    if (i % 2 == 0) deq.push_back(a);
    else deq.push_front(a);
  }

  if (n % 2 == 1) reverse(deq);

  cout << deq.front(); deq.pop_front();
  while (!deq.empty()) {
    cout << " " << deq.front();
    deq.pop_front();
  }
  outl("");
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  srand((unsigned)time(NULL));
  fix(12);

  solve();
}


Measured memory_bytes: 4344
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
        int k = sc.nextInt();
        k = Math.min(k,41);     
        int [] in = new int [n];
        int [] in2 = new int [n];
        for(int i=0;i<n;i++){
                             in[i] = sc.nextInt();
                            }
        for(int j=0;j<k;j++){
        for(int i=0;i<n;i++){in2[i]=0;}
        for(int i=0;i<n;i++){int l = Math.max(0,i-in[i]);  
                             int r = Math.min(n-1,i+in[i]);  
                             in2[l]++; 
                             if(r+1<n) in2[r+1]--;                             
                            }       
        for(int i=1;i<n;i++){in2[i]+=in2[i-1];}
        for(int i=0;i<n;i++){in[i]=in2[i];}
        }
		for(int i=0;i<n;i++){System.out.println(in[i]);
                            }
	}
}


Measured memory_bytes: 63016
import java.util.*;
import java.util.stream.IntStream;

public class Main {

    public static boolean found = false;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        long a = sc.nextLong();
        long b = sc.nextLong();
        long x = sc.nextLong();

        if (a % x != 0) {
            a += x - (a % x);
        }

        if (a > b) {
            System.out.println("0");
            return;
        }
        long ans = ((b - a) / x) + 1;
        System.out.println(ans);
    }

}

Measured memory_bytes: 21844
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using P = pair<int, int>;
using vi = vector<ll>;
using vvi = vector<vi>;



int main() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, n) {
        cin >> a[i];
    }

    ll sum = 0;
    ll ans = 0;
    rep(i, n) {
        if(a[i] == 0) {
            ans += sum/2LL;
            sum = 0LL;
        } else {
            sum += a[i];
        }
    }
    ans += sum/2LL;

    cout << ans << endl;
}

Measured memory_bytes: 1024
n = int(input())
l = list(map(int, input().split()))

#hoge日めにhoge枚の株券持ち
dp = [-7 for _ in range(n+1)]

dp[0] = 1000

#　i日目の所持金
for i in range(1,n+1):
    dp[i] = dp[i-1]
    for j in range(i):
        buy = dp[j]//l[j]
        tmp = dp[j]%l[j] + buy*l[i-1]
        dp[i] = max(dp[i], tmp)

print(dp[n])

Measured memory_bytes: 8980
while True:
    i = input().split()
    n, x = map(int, i)

    if n == 0 and x == 0:
        break
    count = 0
    for a in range(1, n+1):
        for b in range(a+1, n+1):
            for c in range(b+1, n+1):
                if a+b+c == x:
                    count += 1
    print(count)

Measured memory_bytes: 7672
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//cout << fixed << setprecision(17) << res << endl;
 
int main() {
    string s;
    cin >> s;
    if (s[1] == 'R') {
        cout << "ABC" << endl;
    } else {
        cout << "ARC" << endl;
    }
}


Measured memory_bytes: 3592
s=input()
t=input()

s_t=[-1]*26
t_s=[-1]*26

for i in range(len(s)):
    num_s=ord(s[i])-97
    num_t=ord(t[i])-97
    
    if s_t[num_s]==-1 and t_s[num_t]==-1:
        s_t[num_s]=num_t
        t_s[num_t]=num_s
    elif s_t[num_s]!=num_t or t_s[num_t]!=num_s:
        print("No")
        exit()
    
print("Yes")



Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
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;
}
typedef long long int ll;

#define EPS (1e-7)
#define INF (1 << 30)
#define LLINF (1LL << 60)
#define PI (acos(-1))
#define MOD (1000000007)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

//-------------------------------------

ll GCD(ll a, ll b)
{
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}

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

struct RSQ
{
private:
    ll n;
    vector<ll> node;

public:
    RSQ(vector<ll> &v)
    {
        ll sz = v.size();
        n = 1;
        while (n < sz)
        {
            n *= 2;
        }
        node.resize(2 * n - 1, 0);
        for (ll i = 0; i < sz; i++)
        {
            node[i + n - 1] = v[i];
        }
        for (ll i = n - 2; i >= 0; i--)
        {
            node[i] = GCD(node[2 * i + 1], node[2 * i + 2]);
        }
    }

    ll getgcd(ll a, ll b, ll now = 0, ll l = 0, ll r = -1)
    {
        if (r < 0)
        {
            r = n;
        }
        if (r <= a || l >= b)
        {
            return 0;
        }
        if (a <= l && r <= b)
        {
            return node[now];
        }
        ll vl = getgcd(a, b, 2 * now + 1, l, (l + r) / 2);
        ll vr = getgcd(a, b, 2 * now + 2, (l + r) / 2, r);
        return GCD(vl, vr);
    }
};

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    vector<ll> a(n);
    for (ll i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    RSQ segtree(a);
    ll ans = 0;
    for (ll i = 0; i < n; i++)
    {
        ll left = segtree.getgcd(0, i);
        ll right = segtree.getgcd(i + 1, n);
        chmax(ans, GCD(left, right));
    }
    cout << ans << endl;
}

Measured memory_bytes: 3072
package main

import (
        "fmt"
)

func solution(k, a, b int) string {
        n := 0
        for i := 0; n < b; i++ {
                n = k * i
                if n >= a && n <= b {
                        return "OK"
                }
        }
        return "NG"
}

func main() {
        var k, a, b int
        fmt.Scan(&k, &a, &b)
        fmt.Println(solution(k, a, b))
}

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

ll max(ll a,ll b){
	if(a>=b)
		return a;
	else
		return b;
}
int main(){
	ll n;
	ll w;
	cin>>n>>w;
	ll Wt[n];
	ll va[n];
	for(ll i=0;i<n;i++){
		cin>>Wt[i]>>va[i];
	}
	ll dp[n+1][w+1];
	for(ll i=0;i<=n;i++){
		for(ll j=0;j<=w;j++){
			dp[i][j]=0;
		}
	}
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<=w;j++){
			if(j-Wt[i-1]>=0){
				//cout<<dp[i-1][j]<<" "<<dp[i-1][j-Wt[i-1]]+va[i-1]<<endl;
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-Wt[i-1]]+va[i-1]);
			}
			else
				dp[i][j]=dp[i-1][j];
				
			//cout<<dp[i][j]<<" ";
		}
		//cout<<endl;
	}
	cout<<dp[n][w]<<endl;
}

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

int w, h, k;
char map[7][7];

//最下位bitが0列, bit>>6 & 1が0行
inline int exhaust(unsigned int bit){
  int count = 0;
  for (int i=0;i<h;i++){
  	for (int j=0;j<w;j++){
    	if( !((bit>>i)&1)  && !((bit>>(j+h))&1) )
          if (map[i][j] == '#')
            count++;
    }
  }
  return count;
}

// 脳死全探索
int main(){
  scanf("%d%d%d", &h, &w, &k);
  for (int i=0;i<h;i++){
    scanf("%s", map[i]);
    map[i][w] = '\0';
  }
  int count=0;
  int initialValue = (((1<<(w+h))-1) | ((1<<h)-1));
  for (int i=initialValue;i>=0;--i)
    if (exhaust(i) == k){
      count++;
    }
  printf("%d\n", count);
  return 0;
}


Measured memory_bytes: 1736
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

x, y = map(int, readline().split())
if x <= y:
    if (x >= 0 and y >= 0) or (x <= 0 and y <= 0):
        ans = y - x
    else:
        ans = abs(abs(x) - y) + 1
else:
    if (x > 0 and y > 0) or (x < 0 and y < 0):
        ans = min(abs(x) + abs(y) + 1, abs(abs(y) - abs(x)) + 2)
    elif y == 0:
        ans = abs(x) + 1
    elif x == 0:
        ans = abs(y) + 1
    else:
        ans = abs(x - abs(y)) + 1
print(ans)


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

#define optimizar_io ios_base::sync_with_stdio(0);cin.tie(0);

using namespace std;

int main(){
	optimizar_io;
	int N;
	cin >> N;
	cout << fixed << setprecision(8) << (double)(((N + 1) / 2)) / N;
	return 0;
}


Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n int
	fmt.Scan(&n)
	dic1 := map[rune]int{}
	var s1 string
	fmt.Scan(&s1)
	for _, v := range s1 {
		dic1[v]++
	}
	for range make([]struct{}, n-1) {
		var s2 string
		fmt.Scan(&s2)
		dic2 := map[rune]int{}
		for _, v := range s2 {
			dic2[v]++
		}

		dic3 := map[rune]int{}
		for k, v1 := range dic1 {
			if v2, in := dic2[k]; in {
				dic3[k] = min(v1, v2)
			}
		}
		dic1 = dic3
	}
	seq := []string{}
	for k, v := range dic1 {
		for range make([]struct{}, v) {
			seq = append(seq, string(k))
		}
	}
	sort.Strings(seq)
	for _, v := range seq {
		fmt.Print(v)
	}
	fmt.Println()
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}


Measured memory_bytes: 640
#include <stdio.h>

int main()
{
    int n;
    scanf("%d",&n);

    int p[n];
    int i, count=0;
    for(i=1; i<=n; i++)
        scanf("%d",&p[i]);

    for(i=2; i<n; i++)
    {
        if(p[i]>p[i-1] && p[i]<p[i+1])
            count++;
        else if (p[i]<p[i-1] && p[i]>p[i+1])
            count++;
    }

    printf("%d",count);

    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

int N;
bool p[55555];

int main(){
	cin >> N;
	for (int i = 2; i < 55555; ++i) {
		if (!p[i]) {
			for (int j = i * 2; j < 55555; j += i) {
				p[j] = true;
			}
		}
	}
	for (int i = 6; N; i += 5) {
		if (!p[i]) {
			cout << i << sp;
			--N;
		}
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma warning(disable : 4996)
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>
#include<array>


using namespace std;

#define REP(i, n) for(int i = 0;i < n;++i)
#define REPR(i, n) for(int i = n-1;i >= 0;--i)
#define FOR(i, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), (n))
#define ub(v,n) upper_bound(v.begin(), v.end(), (n))
#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
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; }
typedef pair<int, int>P;
typedef array<int, 3> arr3;
std::random_device rd;
std::mt19937 mt(rd());
constexpr int MOD = 1e9 + 7; constexpr int MAX = 200020;
const double pi = acos(-1); constexpr double EPS = 1e-8;
constexpr ll INF = 1e18;


void solve() {
	int N, L; cin >> N >> L;
	vector<int>A(N);
	int idx = -1;
	REP(i, N)cin >> A[i];
	REP(i, N - 1) {
		if (A[i] + A[i + 1] >= L)idx = i;
	}
	if (idx == -1) {
		print("Impossible"); return;
	}
	else {
		print("Possible");
		vector<int>ans;
		REP(i, N-1) {
			if (i == idx)break;
			ans.push_back(i);
		}
		REPR(i, N - 1) {
			if (i == idx)break;
			ans.push_back(i);
		}
		ans.push_back(idx);
		REP(i, N - 1) {
			print(ans[i] + 1);
		}
	}
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//int q; cin >> q;
	//while (q--)
	solve();
}



Measured memory_bytes: 2548
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <map>
using namespace std;
int main() {
    /*
    string num;
    int inputValue;
    vector<int> list;
  
    while(getline(cin, num))
    {
        int a,b;
        sscanf(num.c_str(), "%d %d",&a,&b);
        int sum = a+b;
        int digit = 0;
        while( sum != 0)
        {
            sum = sum/10;
            digit++;
        }
        cout << digit << endl;
   //     cout << a-b <<endl;
    }
  
    */
   for(int x=1  ; x < 10 ; x ++)
{
    for(int y =1 ; y < 10; y ++)
    {
        cout << x << "x" << y << "=" << x*y << endl;
    }
}
    return 0;
}



Measured memory_bytes: 3080
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
using namespace std;

int main (){
        long long a,b;
        long long Ans;
        cin >> a>>b;
        
        if(a*b==15){
            cout << "*";
        }else if (a+b==15){
        	cout << "+";
        }else {
        	cout << "x";
        }

}


Measured memory_bytes: 256
N, Q = [int(_) for _ in input().split()]
S = '.' + input() + '.'
TD = [input().split() for _ in range(Q)]


def check(x):
    for t, d in TD:
        if S[x] == t:
            if d == 'L':
                x -= 1
                if x == 0:
                    return -1
            else:
                x += 1
                if x == N + 1:
                    return 1
    return 0


#to_left_end
ok = 0
ng = N + 1

while ng - ok > 1:
    mid = (ok + ng) // 2
    if check(mid) == -1:
        ok = mid
    else:
        ng = mid
l = ok

#to_right_end
ok = N + 1
ng = 0
while ok - ng > 1:
    mid = (ok + ng) // 2
    if check(mid) == 1:
        ok = mid
    else:
        ng = mid
r = ng
print(r - l)

# https://img.atcoder.jp/exawizards2019/editorial.pdf


Measured memory_bytes: 39344
solve :: [Char] -> Int -> String
solve a b
 | null a    = if (b `mod` 9) == 0 then "Yes" else "No"
 | otherwise = solve (tail a) (b + aInt)
   where aInt = (fromEnum (head a)) - 48

main = do
 a <- getLine :: IO [Char]
 putStr $ solve a 0

Measured memory_bytes: 11804
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#define ALL(X) X.begin(), X.end()
#define SZ(A) int((A).size())
#define RALL(X) X.rbegin(), X.rend()
#define FOR(B) for (size_t i = 0; i < B; i++)
#define FORE(B) for (size_t i = 1; i <= B-1; i++)
#define FORC(A, B) for (size_t i = A; i < B; i++)
#define PRINT(X) cout << X << endl
#define PRINTALL(E, X) { FOR(X) {cout << E[i] << endl; } }
#define READALL(V, N) FOR(N) {int x; cin >> x; V.push_back(x); }
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL>VLL;
typedef vector<PII> VPII;
typedef map<int, int> MII;
typedef map<string, int> MSI;


int main() {

  string s = "";
  LL k = 0;
  cin >> s >> k;
  int pos = 0;

  for(int q = 0; q < s.size(); q++){
      if(s[q] != '1'){
          pos = q + 1;
          q = s.size();
      }
  }

    if(pos == 0){
        pos = s.size();
    }

  if(k < pos){
      cout << 1 << endl;
  }else{
      cout << s[pos - 1] << endl;
  }

}

Measured memory_bytes: 256
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;

int main() {
  int N, K, L;
  cin >> N >> K >> L;
  vector<vector<int>> G1(N), G2(N);
  for (int i = 0; i < K; i++) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    G1[a].push_back(b);
    G1[b].push_back(a);
  }
  for (int i = 0; i < L; i++) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    G2[a].push_back(b);
    G2[b].push_back(a);
  }
  vector<int> id(N, -1);
  int sz = 0;
  for (int i = 0; i < N; i++) {
    if (id[i] != -1) {
      continue;
    }
    queue<int> q;
    id[i] = sz;
    q.push(i);
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (int u : G1[v]) {
        if (id[u] == -1) {
          id[u] = sz;
          q.push(u);
        }
      }
    }
    ++sz;
  }
  vector<int> cnt(sz, 0), res(N);
  vector<bool> used(N, false);
  for (int i = 0; i < N; i++) {
    if (used[i]) {
      continue;
    }
    vector<int> vs;
    vs.push_back(i);
    used[i] = true;
    for (int j = 0; j < vs.size(); j++) {
      int v = vs[j];
      for (int u : G2[v]) {
        if (!used[u]) {
          vs.push_back(u);
          used[u] = true;
        }
      }
    }
    for (int v : vs) {
      ++cnt[id[v]];
    }
    for (int v : vs) {
      res[v] = cnt[id[v]];
    }
    for (int v : vs) {
      --cnt[id[v]];
    }
  }
  for (int x : res) {
    cout << x << " ";
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 17996
#include <iostream>                                                             
#include <vector>                                                               
#include <algorithm>                                                            
                                                                                
using namespace std;                                                            
                                                                                
int main(void) {                                                                
  int n;                                                                        
  vector<int> a;                                                                
                                                                                
  cin >> n;                                                                     
  for (int i(0); i < n; i++) {                                                  
    int tmp;                                                                    
    cin >> tmp;                                                                 
    a.push_back(tmp);                                                           
  }                                                                             
                                                                                
  int min = *min_element(a.begin(), a.end());                                   
  int max = *max_element(a.begin(), a.end());                                   
                                                                                
  cout << max - min;                                                            
  return 0;                                                                     
}    

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define IOS ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define PI acos(-1)
#define EPS 1e-5
#define sz(v) ((int)(v).size())
#define all(v) v.begin(),v.end()
#define forn(i, n) for(ll i=0;i<(ll)n;i++)
#define fi first
#define se second
 

int main() {
	int k;
	cin >> k;
	ll s = 0;
	for(int a = 1; a <= k; a++) {
		for(int b = 1; b <= k; b++) {
			for(int c = 1; c <= k; c++) {
				s +=__gcd( __gcd(a,b), c);
			}
		}
	}
	cout << s << endl;

	return 0;
}



Measured memory_bytes: 3636
#include<iostream>
#include<string.h>
using namespace std;

int main() {
	int loop = 0;
	char s[200001];
	int len;
	int front, back;
	front = back = 0;

	cin >> s;
	len = strlen(s);
	while (s[loop++] != 'A')front++;
	loop = len + 1;
	while (s[loop--] != 'Z')back++;

	cout << len - front - back + 2 << "\n";
	return 0;
}

Measured memory_bytes: 384
H,W = map(int,input().split())
l = [[]]
for i in range(H):
  l.append([0]+list(map(int,input().split())))

ans = []
y = 1
x = 1
xstock = 0
ystock = 0
seen = [[False for i in range(W+2)] for j in range(H+2)]
seen[1][1] = True

while True:
  if xstock > 0 and ystock > 0:
    ans.append([ystock,xstock,y,x])
    xstock = x 
    ystock = y
  if l[y][x]%2 == 1:
    if xstock == 0 and ystock == 0:
      xstock = x 
      ystock = y
    elif xstock > 0 and ystock > 0:
      xstock = 0
      ystock = 0
  #マス目の移動
  #右
  if x+1 <= W and seen[y][x+1] == False:
    x = x+1
    y = y
    seen[y][x] = True
    continue
  #左
  elif x-1 >= 1 and seen[y][x-1] == False:
    x = x-1
    y = y
    seen[y][x] = True
    continue
  #下
  elif y+1 <= H:
    x = x
    y = y+1
    seen[y][x] = True
    continue
  #止まったら
  break
###
N = len(ans)
print(N)
for i in range(N):
  print(*ans[i])   

Measured memory_bytes: 28188
x=input().split()
for i in range(2):
    if x[i]=='A':
        x[i]=10
    elif x[i]=='B':
        x[i]=11
    elif x[i]=='C':
        x[i]=12
    elif x[i]=='D':
        x[i]=13
    elif x[i]=='E':
        x[i]=14
    else:
        x[i]=15
if x[0]==x[1]:
    print('=')
elif x[0]<x[1]:
    print('<')
else:
    print('>')


Measured memory_bytes: 3064
#include <stdio.h>
int main(void){
    int n;
    scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }

    double average = 0;
    for (int i = 0; i < n; i++){
        average += a[i];
    }
    average /= n;

    int tmp = 10000;
    int ans = 0;
    for (int i = 0; i < n; i++){
        if ((a[i] - average) * (a[i] - average) < (tmp - average) * (tmp - average)){
            tmp = a[i];
            ans = i;
        }
    }
    printf("%d\n", ans);

    return 0;
}


Measured memory_bytes: 128
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;

int main(){
	int n;
	int a,b,c,d;
	scanf("%d",&n);
	a = n % 10;
	b = n % 100 / 10;
	c = n % 1000 / 100;
	d = n / 1000;
	if((a == b&&b == c)||(b == c&&c == d))
		printf("Yes\n");
	else
		printf("No\n");
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>

using namespace std;

#define N 8
#define FREE -1
#define NOT_FREE 1

bool X[N][N];
int row[N], col[N];
int lowLeft[N * 2 - 1], lowRight[N * 2 - 1];

void printBoard() {
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (X[i][j] && row[i] != j)
				return;
		}
	}
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (row[i] == j)
				cout << "Q";
			else
				cout << ".";
		}
		cout << endl;
	}
}

void backTrack(int i) {
	if (i == N) {
		printBoard();
		return;
	}
	for (int j = 0; j < N; ++j) {
		if (col[j] == NOT_FREE || lowLeft[i + j] == NOT_FREE || lowRight[i - j + N - 1] == NOT_FREE)
			continue;
		row[i] = j;
		col[j] = lowLeft[i + j] = lowRight[i - j + N - 1] = NOT_FREE;
		backTrack(i + 1);
		row[i] = col[j] = lowLeft[i + j] = lowRight[i - j + N - 1] = FREE;
	}
}

int main() {
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			X[i][j] = false;
		}
	}
	for (int i = 0; i < N; ++i) {
		row[i] = col[i] = FREE;
	}
	for (int i = 0; i < N * 2 - 1; ++i) {
		lowLeft[i] = lowRight[i] = FREE;
	}

	int k;
	scanf("%d", &k);
	for (int i = 0; i < k; ++i) {
		int r, c;
		scanf("%d %d", &r, &c);
		X[r][c] = true;
	}
	backTrack(0);

	return 0;
}

Measured memory_bytes: 3196
//A.cpp
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const ll mod=1e9+7;

int main(){
  string s,t;
  cin >> s >> t;
  s = t + s;
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 256
n, a, b, c, d = map(int, input().split())
s = list(input())
last = ""
for i in range(a, c):
    if last == "#" and s[i] == "#":
        print("No")
        exit()
    last = s[i]
last = ""
for i in range(b, d):
    if last == "#" and s[i] == "#":
        print("No")
        exit()
    last = s[i]
last = ""
if c > d:
    flag = True
    s[b - 1] = "#"
    for i in range(a, c):
        if last == "#" and s[i] == "#":
            flag = False
        last = s[i]
    s[b - 1] = "."
    count = 0
    for i in range(b - 1, d + 1):
        if s[i] == ".":
            count += 1
            if count == 3:
                flag = True
        else:
            count = 0
    if flag:
        print("Yes")
    else:
        print("No")
else:
    print("Yes")


Measured memory_bytes: 4916
#include <iostream>

int main(int argc, char *argv[]) {
  int x1, y1, x2, y2;
  std::cin >> x1 >> y1 >> x2 >> y2;
  int x = x2, y = y2, dx = x2 - x1, dy = y2 - y1;
  for (int i = 0; i < 2; ++i) {
    std::swap(dx, dy);
    dx = -dx;
    x += dx;
    y += dy;
    std::cout << x << " " << y << std::endl;
  }
}


Measured memory_bytes: 3200
def main():
    x = input()
    x1, x2, x3 = x.split(' ') 
    a = int(x1)
    b = int(x2)
    c = int(x3)
    if a < b < c:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

Measured memory_bytes: 7768
const inlt = new Intl.NumberFormat("ja-JP", {
  minimumIntegerDigits: 6,
  useGrouping: false
})
const pad = (s) => inlt.format(s)

const solve = (input) => {
  const [head, ...l] = input.split("\n")
  const mm = l.map((v, l) => {
    const [pref, year] = v.split(" ").map(Number)
    return {
      idx: l,
      pref,
      year
    }
  })
  let r = []
  let mm2 = mm.sort((a, b) => a.year - b.year)
  let prefIdx = []
  mm2.map(({ idx, pref, year }) => {
    if (prefIdx[pref] === undefined) {
      prefIdx[pref] = 1
    }
    r[idx] = `${pad(pref)}${pad(prefIdx[pref])}`
    prefIdx[pref]++
  })
  return r.join("\n")
}

if (process.env.NODE_ENV === "test") {
  module.exports = (input) => solve(input.trim())
} else {
  const input = require("fs").readFileSync("/dev/stdin", "utf8")
  console.log(solve(input.trim()))
}


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

#define int long long
#define double long double
#define incin(n) int (n); cin >> (n)
#define uniq(v) sort((v).begin(),(v).end()); (v).erase(unique((v).begin(),(v).end()),(v).end());
#define steprap(i,n,s) for(int (i)=0;i<(s)*(n);(i)+=(s))
#define rap(i,n) steprap((i),(n),1)

using intV = std::vector<int>;

using namespace std;
namespace math
{
	double PI = 3.14159265359;
	int step(int n);
	int ncr(int n,int r);
	int npr(int n,int r);
	int gcm(int a,int b);
	int lcm(int a,int b);

	int step(int n){
		if(n<=1){
			return 1;
		}else{
			return n * step(n-1);
		}
	}
	int ncr(int n,int r){
		for(int i=1;i<r;i++){
			n *= n-i;
		}
		for(int i=1;i<r;i++){
			r *= r-1;
		}
		return n/r;
	}
	int npr(int n,int r){
		for (int i = 1; i < r; ++i)
		{
			n *= n-1;
		}
		return n;
	}
	int gcm(int a,int b){
		int p=max(a,b);
		int q=min(a,b);
		int r;
		while(true){
			if(p%q==0){
				return q;
			}
			r = p%q;
			p=q;
			q=r;
		}
	}
}

using namespace std;
// using StringMap = std::vector<std::vector<char>> map(h+2,vector<char>(w+2,'#'));
namespace tmp {
    template <typename T> bool inArry(T x,vector<T> v);
    template <typename T> void input(int n,vector<T> &v);

    template <typename T> bool inArry(T x,vector<T> v){
        int l = v.size();
        for(int i=0;i<l;i++){
            if(x==v[i]){
                return true;
            }
        }
        return false;
    }
    
    template <typename T> void input(int n,vector<T> &v){
        for(int i=0;i<n;i++){
            cin >> v.at(i);
        }
    }
}

using namespace std;

signed main (){
	char c;
	cin >> c;
	if(c=='a'||c=='i'||c=='u'||c=='e'||c=='o'){
		cout<<"vowel"<<endl;
	}else{
		cout<<"consonant"<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
solve :: Int -> Int
solve n = minimum $ map f [1..lim]
    where
        lim :: Int
        lim = floor . sqrt . fromIntegral $ n
        f :: Int -> Int
        f i
            | r == 0 = i + q - 2
            | otherwise = 10^13
                where
                    (q,r) = divMod n i

main = do
    n <- readLn :: IO Int
    print $ solve n 

Measured memory_bytes: 892
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
using namespace std;

int main() {
  int N,N2;
  cin >> N >> N2;
  int ans;
  
  ans = (N*3 + N2)/2;
  cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;
import java.math.*;
import java.lang.*;
import java.io.*;
 
public class Main{
  public static void main(String args[]) throws IOException{
    Scanner s=new Scanner(System.in);
   
    String ss=s.nextLine();
    String tt=s.nextLine();
    
    int c=0;
    for(int i=0;i<3;i++){
      if(ss.charAt(i)==tt.charAt(i))
        c++;
    }
    System.out.println(c);
  }
}
    
    
  

Measured memory_bytes: 23252
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	map<int, int> mc;
	int a = 0, b = 0;
	int n;
	cin >> n;
	while (n--)
	{
		int x;
		cin >> x;
		mc[x]++;
	}
	for (auto &p : mc)
	{
		if (p.second >= 4) a = b = p.first;
		else if (p.second >= 2)
		{
			b = a;
			a = p.first;
		}
	}
	cout << 1LL*a * b << endl;
	return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define all(x) x.begin(),x.end()

int main(){
  ll n;
  cin >> n;
  ll ans = 0;
  vector<ll> p;
  ll tmp,x=-1;
  for(ll i=0;i<n;i++){
    cin >> tmp;
    if(tmp == x+1){
      p.push_back(x);
    }
    x = tmp;
  }
  for(ll i=0;i<n;i++){
    cin >> tmp;
    ans += tmp;
  }
  if(p.size() == 0){
    for(ll i=1;i<n;i++){
      cin >> tmp;
    }
    cout << ans << endl;
  }
  else{
    sort(all(p));
    reverse(all(p));
    x = p.back();
    p.pop_back();
    for(ll i=1;i<n;i++){
      cin >> tmp;
      if(i==x){
        ans += tmp;
        x = p.back();
        p.pop_back();
      }
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
  int i,n,a[50]={0},dem=0;
  scanf("%d", &n);
  for (i=0; i<n; i++)
    {
      scanf("%d", &a[i]);
      if (a[i]!=i+1) dem++;
    }
  if (dem>2) printf("NO");
   else printf("YES");
  return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
const int N = 1e5 + 5;
const int mod = 1e9 + 7; 
using namespace std; 

int n, m, x[N], y[N], ans1, ans2; 

template < typename T >
inline T read()
{
	T x = 0, w = 1; char c = getchar();
	while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * w; 
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("cpp.in", "r", stdin);
#endif
	n = read <int> (), m = read <int> ();
	for(int i = 1; i <= n; i++) x[i] = read <int> ();
	for(int j = 1; j <= m; j++) y[j] = read <int> ();
	for(int i = 1; i < n; i++) ans1 = (1ll * (x[i + 1] - x[i]) * i % mod * (n - i) + ans1) % mod;
	for(int i = 1; i < m; i++) ans2 = (1ll * (y[i + 1] - y[i]) * i % mod * (m - i) + ans2) % mod;
	printf("%lld\n", 1ll * ans1 * ans2 % mod); 
	return 0; 
}


Measured memory_bytes: 4460
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <cassert>

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

using namespace std;
typedef long long int ll;
const ll INF = 1000000000000000000;
const double PI = acos(-1);

int main()
{
    int x, y, a, b, c;
    cin >> x >> y >> a >> b >> c;
    vector<int> p(a);
    vector<int> q(b);
    vector<int> r(c);
    rep(i, a) cin >> p[i];
    rep(i, b) cin >> q[i];
    rep(i, c) cin >> r[i];

    sort(p.begin(), p.end());
    sort(q.begin(), q.end());

    vector<int> eat;
    rep(i, x) {
        eat.push_back(p[a - 1 - i]);
    }
    rep(i, y) {
        eat.push_back(q[b - 1 - i]);
    }
    rep(i, c) {
        eat.push_back(r[i]);
    }

    sort(eat.begin(), eat.end());

    ll ans = 0;
    rep(i, x+y) {
        ans += eat[eat.size() - 1 - i];
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

const int maxn = 200010;

int n, X, Y;
int tag[maxn], vis[maxn];

struct Tree {
	int l[maxn], dep[maxn], fa[maxn][20], e, r;

	Tree() {memset(l, -1, sizeof(l));}

	struct Edge {
		int v, x;
	} E[maxn<<1];

	inline void addEdge(int u, int v) {
		E[e].v = v, E[e].x = l[u], l[u] = e++;
		E[e].v = u, E[e].x = l[v], l[v] = e++;
	}

	void dfs(int u, int f) {
		fa[u][0] = f;
		for (int i = 1; i < 20; i++) fa[u][i] = fa[fa[u][i-1]][i-1];
		for (int p = l[u]; p >= 0; p = E[p].x) {
			int v = E[p].v;
			if (v != f) {
				dep[v] = dep[u] + 1;
				dfs(v, u);
			}
		}
	}

	void init(int rt) {
		r = rt;
		dfs(r, 0);
	}

	int lca(int u, int v) {
		if (dep[u] < dep[v]) swap(u, v);
		if (dep[u] > dep[v]) {
			int c = dep[u] - dep[v];
			for (int i = 0; i < 20; i++) {
				if (c & (1 << i)) {
					u = fa[u][i];
				}
			}
		}
		if (u == v) return u;
		for (int i = 19; i >= 0; i--) {
			if (fa[u][i] != fa[v][i]) {
				u = fa[u][i], v = fa[v][i];
			}
		}
		return fa[u][0];
	}

	int dis(int u, int v) {
		return dep[u] + dep[v] - 2 * dep[lca(u, v)];
	}
} T1, T2;

void dfs_vis(int u, int f) {
	vis[u] = 1;
	for (int p = T1.l[u]; p >= 0; p = T1.E[p].x) {
		int v = T1.E[p].v;
		if (v != f) {
			// 此时 Y 的深度为 T1.dep[u]
			if (T2.dep[v] > T1.dep[u] + 1) {
				dfs_vis(v, u);
			}
		}
	}
}

int main() {
	scanf("%d%d%d", &n, &X, &Y);
	for (int i = 1; i < n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		T1.addEdge(a, b);
	}
	for (int i = 1; i < n; i++) {
		int c, d; 
		scanf("%d%d", &c, &d);
		T2.addEdge(c, d);
	}
	T1.init(X), T2.init(Y);
	for (int u = 1; u <= n; u++) {
		for (int p = T1.l[u]; p >= 0; p = T1.E[p].x) {
			int v = T1.E[p].v;
			if (T2.dis(u, v) > 2) {
				tag[u] = 1;
			}
		}
	}
	dfs_vis(X, 0);
	int ans = 0;
	for (int u = 1; u <= n; u++) {
		if (vis[u]) {
			if (tag[u]) ans = 0x3f3f3f3f;
			else ans = max(ans, T2.dep[u]);
		}
	}
	if (ans < 0x3f3f3f3f) printf("%d\n", ans << 1);
	else puts("-1");
	return 0;
}

Measured memory_bytes: 47872
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
// #define mt make_tuple
//typedef tuple<pii,int,int> tp;
//typedef vector<tp> vt;
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;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-7;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
	int n;
	cin>>n;
	vp in(n);
	rep(i,n)cin>>in[i].first>>in[i].second;
	sort(all(in));
	cout<<in[n-1].first+in[n-1].second<<endl;
}








Measured memory_bytes: 1024
# 先にクエリを蓄積してから親のカウンターを子に分配

from collections import deque

N,Q=map(int,input().split())
vtx=[[] for _ in range(N)]
pnt=[-1 for _ in range(N)]
cnt=[0 for _ in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  vtx[a-1].append(b-1)
  vtx[b-1].append(a-1)
pnt[0]=0
que=deque([0])
while que:
  v=que.popleft()
  for w in vtx[v]:
    if pnt[w]==-1:
      pnt[w]=v
      que.append(w)
for i in range(Q):
  p,x=map(int,input().split())
  cnt[p-1]+=x
que=deque([0])
while que:
  # print(cnt)
  v=que.popleft()
  for w in vtx[v]:
    if w!=pnt[v]:
      cnt[w]+=cnt[v]
      que.append(w)
for c in cnt:
  print(c)

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

int main() {
	// your code goes here
	int n, X, D = 0; cin >> n >> X;
	while (n--) {
		int xi; cin >> xi;
		D = __gcd(D, abs(X - xi));
	}
	cout << D;
	return 0;
}

Measured memory_bytes: 256
S = input()
count = 0

if S.count("R") == 0:
    count = 0
elif S.count("R") == 1:
    count= 1
elif S.count("R") == 2:
    if S == "RSR":
        count = 1
    else:
        count = 2
else:
    count = 3
    
print(count)

Measured memory_bytes: 9104
#include<stdio.h>
#include<memory.h>
#define SMAX 330
int C[11][SMAX+1][1<<10];
int count(int n, int s, int U){
	int i, c, b;
	if(C[n][s][U] >= 0)
		return C[n][s][U];
	if(n == 0) {
		if (s == 0)
			c = 1;
		else
			c = 0;
	} else {
		c = 0;
		for(i = 0; i <= 9; i ++){
			b = 1<<i;
			if(!(U & b) && n*i <= s){
				c += count(n-1, s-n*i, U|b);
			}
		}
	}
	return C[n][s][U] = c;
}
int main(){
	int n, s, U, c;
	while(~scanf("%d%d", &n, &s)){
		memset(C,0xFF,sizeof(C));
		U=0;
		if (s <= SMAX)
			c = count(n, s, U);
		else
			c = 0;
		printf("%d\n", c);
	}
	return 0;
}

Measured memory_bytes: 14000
#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() {
  int n,m; cin >> n >> m;
  vector<vector<int>> c(n+1, vector<int>());
  rep(i,m) {
    int a, b; cin >> a >> b;
    c[a].push_back(b);
    c[b].push_back(a);
  }

  vector<bool> ed(n+1,false);
  queue<int> q;
  ed[0] = true;
  int ans = -1;
  for (int k = 1; k<n+1; k++) {
    if (!ed[k]) {
      q.push(k);
      ans++;
    }
    while (!q.empty()) {
      int i = q.front(); q.pop();
      ed[i] = true;
      for (auto j : c[i]) {
        if (ed[j]) continue;
        q.push(j);
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 8448
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;
typedef pair<long long ,long long> ii; 	
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll a,b,c;
	cin >> a >> b >> c;
	if (a+b+c >= 22) cout << "bust" << endl;
	else cout << "win" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <algorithm>
#define N 210
using namespace std;

int n, m;
int d[N][N];

bool check(){
	for (int k = 0; k < m; k++){
		for (int i = 0; i < m; i++){
			for (int j = 0; j < m; j++){
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}

	for (int i = 0; i < m; i++){
		if (d[i][i] < 0){
			return false;
		}
	}
	return true;
}

int main(){
	string a, b, s;
	int x;
	char c;

	while (cin >> n && n){
		m = n * 2;
		for (int i = 0; i < N; i++){
			for (int j = 0; j < N; j++){
				d[i][j] = 100000000;
			}
			d[i][i] = 0;
		}
		map<string, int> units;
		m = 0;
		for (int i = 0; i < n; i++){
			cin >> x >> a >> c;
			cin >> x >> c;
			cin >> x >> b;

			if (units.find(a) == units.end()){
				units[a] = m++;
			}
			if (units.find(b) == units.end()){
				units[b] = m++;
			}

			int an = units[a], bn = units[b];

			d[an][bn] = -x;
			d[bn][an] = x;
		}

		if (check()){
			cout << "Yes" << endl;
		}else{
			cout << "No" << endl; 
		}
	}
	return 0;
}

Measured memory_bytes: 1404
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#pragma warning(disable:4996)
#include <stdio.h>
#include <string>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <functional>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <list>
#include <set>
#include <map>
#include <iomanip> 
#include <ctime>
#include <numeric>
#include <cassert>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<string, int> P;
typedef vector<vector<int>> Graph;

const double PI = 3.14159265358979323846;

const int mod = 1000000007;

int main(int argc, char *args[]) {
	ll h, w; cin >> h >> w;
	if (h == 1 | w == 1) {
		cout << 1 << endl;
		return 0;
	}
	if (h % 2 == 0) {
		cout << w * (h / 2) << endl;
	}
	else {
		cout << w * (h / 2) + (w + 1) / 2 << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
using namespace std;

int main(void){
	int n;
	double x[2],y[2],r[2];
	double lo;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		cin >> x[0] >> y[0] >> r[0] >> x[1] >> y[1] >> r[1];
		lo=sqrt(pow(abs(x[0]-x[1]),2)+pow(abs(y[0]-y[1]),2));
		if(r[0]>r[1] && r[0]>r[1]+lo)printf("2\n");
		else if(r[1]>r[0] && r[1]>r[0]+lo)printf("-2\n");
		else if(lo<=r[0]+r[1])printf("1\n");
		else printf("0\n");
	}
    return 0;
}

Measured memory_bytes: 0
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}
use std::collections::HashMap;
use std::cmp::{max,min};
fn main(){
    input!{
        n:usize,
    }
    println!("{}",n*n*n);
}


fn is_prime(x:i64) -> bool {
    if x == 2 {return true;}
    if x < 2 || x % 2 == 0 {return false;}
    let mut j = 3;
    while j <= (x as f64).sqrt() as i64 {
        if x % j == 0 {
            return false;
        }
        j += 2;
    }
    true
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

int32_t main(){
	IOS;
	int n;
	cin >> n;
	int k = n%10;
	set<int> st = {0, 1, 6, 8};
	if( k == 3 ){
		cout << "bon" << endl;
	}else if( st.find(k) != st.end() ){
		cout << "pon" << endl;
	}else{
		cout << "hon" << endl;
	}
	return 0;
}

Measured memory_bytes: 3644