akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i < (n + 1); ++i)
using namespace std;
using ll = long long;
const int INF = +100100100;
// typedef pair<int,int> P;

vector<int> D(150, INF);
vector<vector<int>> M(150, vector<int>(150));
int n;

void bfs()
{
    int s = 0;
    queue<int> Q;
    Q.push(s);
    D[0]=0;
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        rep(v, n)
        {
            // 訪れたことがない
            if (D[v] == INF&&M[u][v]==1)
            {
                D[v] = D[u] + 1;
                Q.push(v);
            }
        }
    }
    rep(i,n)if(D[i]==INF)D[i]=-1;
}

int main()
{
    cin >> n;
    vector<list<int>> L(n);
    rep(i, n)
    {
        int u, e;
        cin >> u >> e;
        rep(j, e)
        {
            int v;
            cin >> v;
            --v;
            L[i].push_back(v);
        }
    }
    
    rep(i, n)
    {
        rep(j, n)
        {
            list<int>::iterator it = find(L[i].begin(), L[i].end(), j);
            if (it != L[i].end())
            {
                M[i][j] = 1;
                L[i].erase(it);
            }
        }
    }
    bfs();
    rep(i,n){
        printf("%d %d\n",i+1,D[i]);
    }
    return 0;
}


Measured memory_bytes: 3344
//============================================================================
// Name        : ITP_1_6_A.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int main() {
	int n;
	vector<int> a;
	cin >> n;
	a.resize(n);
	for(int i=0;i<n;++i) {
		cin >> a[i];
	}
	for(int i=n-1;i>0;--i) {
		printf("%d ",a[i]);
	}
	printf("%d\n",a[0]);
	return 0;
}

Measured memory_bytes: 3188
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;

double dist(vector<double> &v, int n){
	if(n==-1){
		double r=v[0];
		for(int i=1;i<v.size();i++)r=max(r,v[i]);
		return r;
	}
	double s=0;
	for(int i=0;i<v.size();i++)s+=pow(v[i],n);
	return pow(s,1.0/n);
}
int main(){
	int n;
	scanf("%d",&n);
	vector<double> a(n),b(n);
	for(int i=0;i<n;i++)scanf("%lf",&a[i]);
	for(int i=0;i<n;i++)scanf("%lf",&b[i]);
	for(int i=0;i<n;i++)a[i]=fabs(a[i]-b[i]);
	printf("%f\n%f\n%f\n%f\n",dist(a,1),dist(a,2),dist(a,3),dist(a,-1));
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<string> W(n);
  REP(i, n) cin >> W[i];
  bool ok = true;
  REP(i, n) {
    REP(j, n) {
      if(j == i) {
        break;
      }
      if(W[i] == W[j]) {
        ok = false;
      }
    }
  }
  for(int i = 0; i < n - 1; i++) {
    string word1 = W[i];
    string word2 = W[i + 1];
    if(word1[word1.size() - 1] != word2[0]) {
      ok = false;
    }
  }

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

Measured memory_bytes: 256
/* 
chirag11032000
Chirag Thakur
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

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

template < typename T > using OrderedSet = tree < T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update >;
template < typename T > using MinPriorityQueue = priority_queue < T, vector < T >, greater < T > >;

#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template < typename Arg1 >
void __f(const char* name, Arg1&& arg1) {
	cerr << name << " : " << arg1 << std :: endl;
}
template < typename Arg1, typename... Args >
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');
	cerr.write(names, comma - names) << " : " << arg1 << " | ";
	__f(comma + 1, args...);
}
#else
#define trace(...)
#endif

#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

const db PI = acos(-1);
const ll LINF = LLONG_MAX;
const int INF = INT_MAX, MOD = 1e9 + 7, N = 1e5 + 10;

void testCase();

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	testCase();
	cerr << "Time taken: " << int((clock() * 1000.) / CLOCKS_PER_SEC) << "ms\n";
	return 0;
}

void testCase() {
	int n;
	cin >> n;
	vector < int > v(n + 2), pref(n + 2), suff(n + 2);
	for (int i = 1; i <= n; ++i) {
		cin >> v[i];
	}
	for (int i = 1; i <= n; ++i) {
		pref[i] = __gcd(pref[i - 1], v[i]);
	}
	for (int i = n; i >= 1; --i) {
		suff[i] = __gcd(suff[i + 1], v[i]);
	}
	int mx = -INF;
	for (int i = 1; i <= n; ++i) {
		mx = max(mx, __gcd(pref[i - 1], suff[i + 1]));
	}
	cout << mx << "\n";
}

Measured memory_bytes: 1408
#include <iostream>
#include <cmath>
#include <bitset>
using namespace std;
int it,h,w,i,j;
struct pai
{
    int x,y;
} a[85][85];
int m[85][85];
struct poz
{
    int maxi;
    bitset <6405> fr;
} dp[85][85];
int main()
{
    cin>>h>>w;
    for(i=1; i<=h; i++)
    {
        for(j=1; j<=w; j++)
            cin>>a[i][j].x;
    }
    for(i=1; i<=h; i++)
    {
        for(j=1; j<=w; j++)
            cin>>a[i][j].y;
    }
    for(i=1; i<=h; i++)
        for(j=1; j<=w; j++)
            m[i][j]=abs(a[i][j].x-a[i][j].y);
    dp[1][1].fr[m[1][1]]=1;
    dp[1][1].maxi=m[1][1];
    for(i=1; i<=h; i++)
        for(j=1; j<=w; j++)
        {
            for(it=0;it<=dp[i][j].maxi;it++)
            {
                if(dp[i][j].fr[it])
                {
                    if(it+m[i+1][j]<=6400)
                    {
                        dp[i+1][j].fr[it+m[i+1][j]]=1;
                        dp[i+1][j].maxi=max(dp[i+1][j].maxi, it+m[i+1][j]);
                    }

                    if(abs(it-m[i+1][j])<=6400)
                    {
                        dp[i+1][j].fr[abs(it-m[i+1][j])]=1;
                        dp[i+1][j].maxi=max(dp[i+1][j].maxi, (int)abs(it-m[i+1][j]));
                    }

                    if(it+m[i][j+1]<=6400)
                    {
                        dp[i][j+1].fr[it+m[i][j+1]]=1;
                        dp[i][j+1].maxi=max(dp[i][j+1].maxi, it+m[i][j+1]);
                    }

                    if(abs(it-m[i][j+1])<=6400)
                    {
                        dp[i][j+1].fr[abs(it-m[i][j+1])]=1;
                        dp[i][j+1].maxi=max(dp[i][j+1].maxi, (int)abs(it-m[i][j+1]));
                    }

                }

            }
        }
    for(i=0;i<=dp[h][w].maxi;i++)
        if(dp[h][w].fr[i])
    {
        cout<<i;
        return 0;
    }
    return 0;
}


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

typedef long long ll;
const int N = 500054, mod = 998244353;

int n, m;
int inv[N];

ll PowerMod(ll a, int n, ll c = 1) {for (; n; n >>= 1, a = a * a % mod) if (n & 1) c = c * a % mod; return c;}

int main() {
	int i, cur; ll ans, coef;
	scanf("%d%d", &n, &m), inv[1] = 1;
	if (n > m) std::swap(n, m);
	ans = cur = PowerMod(n + 1, m, PowerMod(m + 1, n));
	coef = PowerMod((n + 1ll) * (m + 1ll) % mod, mod - 2, mod - 1);
	for (i = 2; i <= n; ++i) inv[i] = ll(mod - mod / i) * inv[mod % i] % mod;
	for (i = 1; i <= n; ans += cur, ++i)
		cur = cur * coef % mod * (n - i + 1ll) % mod * (m - i + 1ll) % mod * inv[i] % mod;
	printf("%d\n", int(ans % mod));
	return 0;
}

Measured memory_bytes: 2176
#include<iostream>

using namespace std;

const static int MAX_N = 100000;

long long N, A, B;
long long X[MAX_N];

long long dp[MAX_N];

int main() {
  cin >> N >> A >> B;

  for (int i = 0; i < N; i++) 
    cin >> X[i];

  dp[0] = 0;
  for (int i = 0; i < N - 1; i++) {
    dp[i + 1] = dp[i] + min((X[i + 1] - X[i]) * A, B);
  }

  cout << dp[N - 1] << endl;

  return 0;
}


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

int main()
{
  int n;
  int ans = 100000;
  cin >> n;
  while( n-- ) {
    ans += ans / 100 * 5;
    if( ans % 1000 > 0 ) {
      ans = ans / 1000 * 1000;
      ans += 1000;
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 1160
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 100005;

int n,ans;
pair<int, int> a[N], pr[N], sf[N];

pair<int,int> hat(pair<int, int> a, pair<int, int> b)
{
	return MP(max(a.first, b.first), min(a.second, b.second));
}

int len(pair<int, int> a)
{
	return max(0, a.second - a.first + 1);
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		scanf("%d%d", &a[i].first, &a[i].second);
	sort(a + 1, a + 1 + n);
	pr[0] = sf[n + 1] = MP(0,mod);
	for (int i = 1; i <= n; i++)
		pr[i] = hat(pr[i - 1], a[i]);
	for (int i = n; i >= 1; i--)
		sf[i] = hat(sf[i + 1], a[i]);
	for (int i = 1; i <= n; i++)
		ans = max(ans, len(hat(pr[i - 1], sf[i + 1])) + len(a[i]));
	for (int i = 1; i < n; i++)
		ans = max(ans, len(pr[i]) + len(sf[i + 1]));
	cout << ans << endl;
	return 0;
}

/*



*/

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
#ifdef ONLINE_JUDGE
#define filename(_ST_) \
		freopen(_ST_".in","r",stdin); \
		freopen(_ST_".out","w",stdout);
#else
#define filename(_ST_)
#endif
char outp[64];
template<typename T>
inline void read(T &x){
	char ch=0; x=0;
	bool sign=false;
	while(ch<'0'||'9'<ch) sign|=ch=='-',ch=getchar();
	while('0'<=ch&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	x=sign?-x:x;
}
template<typename T>
inline void print(T x){
	if(!x){ putchar('0'); return; }
	if(x<0) putchar('-'),x=-x;
	int tot=0;
	while(x) outp[tot++]=x%10+'0',x/=10;
	while(tot) putchar(outp[--tot]);
}
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rt register int
#define read2(_a,_b) read(_a),read(_b)
#define all(item) item.begin(),item.end()
#define read3(_a,_b,_c) read(_a),read(_b),read(_c)
#define For1(f,e,item) for(rt item=f;item!=e;++item)
#define Rep1(f,e,item) for(rt item=f;item!=e;--item)
#define For2(f,e,item) for(rt item=f;item<e;++item)
#define Rep2(f,e,item) for(rt item=f;item>e;--item)
#define For3(f,e,item) for(rt item=f;item<=e;++item)
#define Rep3(f,e,item) for(rt item=f;item>=e;--item)
int n,m;
char Map[1024][1024];
int dp[1024][1024];
const int MOD=1e9+7;
int main(){
	//filename("");
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=0;i<n;++i){
		for(int j=0;j<m;++j){
			cin>>Map[i][j];
		}
	}
	dp[n-1][m-1]=1;
	for(int i=n-1;i>=0;--i){
		for(int j=m-1;j>=0;--j){
			if(Map[i][j]=='.'){
				dp[i][j]=(dp[i][j]+dp[i+1][j]+dp[i][j+1])%MOD;
			}
		}
	}
	cout<<dp[0][0]<<endl;
	return 0;
}

Measured memory_bytes: 5376
x=range(int(input()))
f=lambda a,d,b,c : a*d - b*c 
P=[]
for _ in x:P+=[[int(i) for i in input().split()]]
_=0
P+=[P[0]]
for j in x:_+=f(P[j][0],P[j+1][1],P[j][1],P[j+1][0])
print(_*0.5)

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

int main() {
  int N;
  string S;
  cin >> N >> S;
  int counter = 0;
  rep(i,N-2) {
    if (S.at(i) == 'A') {
      if (S.at(i+1) == 'B') {
        if (S.at(i+2) == 'C') {
          counter++;
    }}}
  }
  cout << counter << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int a[100001];
int main()
{
	int n;
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
		scanf("%d",a+i);
	int ans=0;
	for (int i=1;i<=n;++i)
		if (a[i]==i)
		{
			int j=i;
			while (j<=n&&a[j]==j)
				++j;
			ans+=(j-i+1)/2;
			i=j-1;
		}
	printf("%d",ans);
	return 0;
}


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

// 
int main() {
    int N;
    cin >> N;
    long long a;
    long long modNum = pow(10, 9) + 7;

    long long ans = 0;
    long long total = 0;

    for (int i = 0; i < N; i++) {
        cin >> a;
        ans += total * a;
        ans %= modNum;
        total += a;
        total %= modNum;
    }

    cout << ans;
}


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

using namespace std;
#define int int64_t
#define rep(i, a, n) for (int i = (a); i < (n); ++i)
#define reps(i, a, n) for (int i = (a); i < (n); --i)
#define all(x) (x).begin(), (x).end()
#define gsort(x, n) sort((x), (x + n) greater<int>())
#define rv(s) reverse((s).begin(), (s).end())
#define setout(n, x) setw(n) << setfill(x)
#define Fixed fixed << setprecision(10);
#define pb(x, a) (x).push_back(a)
#define fb(x, a) (x).flont_back(a)
#define eb(x, a) (x).emplaes_back(a)
using pii = pair<int, int>;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const long long mod = 1e9 + 7;

signed main()
{
   cin.tie(nullptr);
   ios_base::sync_with_stdio(false);

   int n,cnt,ans=1;
   string s;
   cin>>n>>s;
   vector<int> x;
   x.resize(27,0);

   rep(i,0,n){
      s[i] -= 'a';
      ++x[s[i]];
   }

   rep(i,0,26){
      if(x[i] != 0){
         cnt = x[i] + 1;
         ans *= cnt;
         ans %= mod;
      }
   }

   cout<<(ans-1)%mod<<'\n';
   return 0;
}

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

int main()
{
  int h,w;
  cin >> h >> w;
  vector<bool> bh(h,0);
  vector<bool> bw(w,0);
  char a[h][w];
  
  for(int i=0;i<h;++i){
    for(int j=0;j<w;++j){
      cin >> a[i][j];
      if(a[i][j]=='#'){
        bh.at(i)=1;
        bw.at(j)=1;
      }
    }
  }
  
  bool kaigyo=0;
  for(int i=0;i<h;++i){
    for(int j=0;j<w;++j){
      if(bh.at(i)&&bw.at(j)){
        cout << a[i][j];
        kaigyo=1;
      }
    }
    if(kaigyo){
      cout << endl;
      kaigyo=0;
    }
  }
  
  return 0;
}

Measured memory_bytes: 256
import collections

n, m = map(int, input().split())
a = list(map(int, input().split()))

d = collections.defaultdict(int)
b = [0] * (n+1)
for i in range(n):
  b[i+1] = b[i] + a[i]

for bi in b:
  d[bi%m] += 1

print(sum([v*(v-1)//2 for v in d.values()]))


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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int n;
vi g[125252];
vi children[125252];

void dfs(int p,int bef){
  for(int to : g[p])if(to!=bef){
    children[p].push_back(to);
    dfs(to,p);
  }
}

int gru(int p){
  int ret = 0;
  for(int to : children[p]){
    ret ^= (gru(to)+1);
  }
  return ret;
}

int main(){
  scanf("%d",&n);
  REP(i,n-1){
    int x,y;
    scanf("%d%d",&x,&y);
    --x;--y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  dfs(0,-1);
  if(children[0].size()==1){
    puts("Alice");
    return 0;
  }
  int a = gru(0);
  puts(a==0?"Bob":"Alice");
  return 0;
}


Measured memory_bytes: 18560
#include <bits/stdc++.h>
using namespace std;
#define   ll long long int
#define maxn 100005

int pos(int n){
    int ans=0;
    for(int i=1;i<=sqrt(n);i++){
        if(n%i==0){
            ans++;
            if(i!=n/i){
                ans++;
            }
        }
    }
    return ans;
}


int main(){

int n;
cin>>n;
ll ans=0;
for(int c=1;c<n;c++){
    ans+=pos(n-c);
}
cout<<ans<<endl;

}


Measured memory_bytes: 3676
#include<stdio.h>

int search(int A[],int n,int key){
	int i=0;
	A[n]=key;
	while(A[i] != key)
		i++;
	return i != n;
}

int main(){
	int i,n,A[10000],q,key,sum=0;

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

	scanf("%d",&q);
	for(i=0;i<q;i++){
		scanf("%d",&key);
		if(search(A,n,key))
			sum++;
	}
	printf("%d\n",sum);

	return 0;
}

Measured memory_bytes: 636
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = 1; i < (int)(n); i++) 
#define dunk(n) cout << n << endl
#define all(a) (a).begin(),(a).end()
typedef pair<int,int> P;
typedef long long ll;

int main() {
    int n;
    cin >> n;
    vector<string> s(n);
    rep(i,n) cin >> s[i];
    sort(all(s));
    int ans = 1;
    rrep(i,n){
        if(s[i-1] == s[i]) continue;
        ans++;
    }
    dunk(ans);
    return 0;
}

Measured memory_bytes: 9608
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <numeric>
#include <iomanip>
#include <tuple>

using namespace std;


int main(){
   int n,m;
   cin>>n>>m;
   vector<int> l(m+2),r(m+2),ta(n+2);
   for(int i=0;i<m;i++){
       cin>>l[i]>>r[i];
       ta[l[i]]++;
       ta[r[i]+1]--;
   }
   for(int i=0;i<=n;i++){
       if(i>0)ta[i]+=ta[i-1];
   }

   int ans=0;
   for(int i=0;i<=n;i++){
       if(ta[i]==m)ans++;
   }
   cout<<ans<<endl;
}

   


Measured memory_bytes: 1408
#include<stdio.h>
#include <assert.h>
#include<math.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
 size_t strlen(const char *s);
#define rep(i,n) for(int i=0;i<n;i++)
#define SOA(array) (sizeof(array)/sizeof(array[0]))

using namespace std;
std::vector<int> graph[10050];//graph頂点数のsize
const int N=100010;
const int P=1000000007;
long long int compare_int(const void *a, const void *b)
{
    return *(long long int*)a - *(long long int*)b;//a-b昇順
}
//絶対値
int ze(int a, int b){
	if(a>b){
		return a-b;
	}else{
		return b-a;
	}
}
int min(int a, int b){
	if(a>b){
		return b;
	}else{
		return a;
	}
}
// a^n mod 
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

// a^{-1} mod 
long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}

//mod掛け算
long long mt(long long a, long long b, long long mod){
	return (a*b)%mod;
}
//配列最小値　mine(array, SOA(array));
int mine(const int* array, size_t size)
{
    assert(array != NULL);
    assert(size >= 1);

    int min = array[0];
    for (size_t i = 1; i < size; ++i) {
        if (min > array[i]) {
            min = array[i];
        }
    }

    return min;
}

//メモ
//	cout<<(n-2)*180<<endl;
//	string s="hoge";
//	cout<<ans<<endl;
//	int  n  ,a  ,b  ,c  ,d  ,e  ,f  ;
//	cin  >>n  >>a  >>b  >>c  >>d  >>e  >>f  ;

/*
	memset(b, '\0', sizeof(b));
初期化*/


/*
	len = strlen(s);
文字列長さ*/


/*
	string s;
	s.size()
*/


/*ソート
	qsort(b, 10, sizeof(int), compare_int);
*/


/*
	char s[N];
	strlen(s)
/*
	if(  <  )puts("Yes");
	else puts("No");
*/
/*文字列比較
if(strcmp(name[i],s)==0)
*/
/*
	graph[a].push_back(b);//graph[a][i番目に入れた]==b
	graph[j].size()	//forで回すときとか

*/


int main(){
	int a,b,m;
	int ans=N;

	cin>>a>>b>>m;
	
	int ai[N];
	int bi[N];
	int c[4][N];
	rep(i,a){
		cin>>ai[i];
	}
	rep(i,b){
		cin>>bi[i];
	}
	rep(i,m){
		cin>>c[0][i]>>c[1][i]>>c[2][i];
		c[3][i]=ai[c[0][i]-1]+bi[c[1][i]-1]-c[2][i];
	}
	int d[]={mine(ai, a)+mine(bi, b),mine(c[3],m)};
	printf("%d\n",mine(d,2));
//	printf("%d\n",ai[0]);

}
	

Measured memory_bytes: 2944
N, P = map(int, input().split())
odd = sum([int(i) % 2 for i in input().split()])
even = N-odd

if odd == 0:
    if P == 0:
        print(2**even)
    else:  # P==1
        print(0)
else:
    print(2**even * (2**odd//2))


Measured memory_bytes: 2940
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<cctype>
#include<string.h>
#include <stdlib.h>

#define PI 3.1415926
void swap(int* x, int* y) {
	int a = *x;
	int b = *y;
	*x = b;
	*y = a;
}
int factorial(int n);
int sum(int n, int*);
int ave(int n, int*);
int min(int n, int*), min(int n, int m);
int max(int n, int*), max(int n, int m);

int main() {
	int N, M, A[2000], B[2000];
	int V[2000] = { 0 };
	int max = 0;
	int ans;
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &A[i]);
	}
	for (int i = 1; i <= M; i++) {
		scanf("%d", &B[i]);
	}
	for (int i = 1; i <= M; i++) {
		for (int j = 1; i <= N; j++) {
			if (A[j] <= B[i]) {
				V[j]++;
				break;
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		//printf("%d\n", V[i]);
		if (max < V[i]) {
			max = V[i];
			ans = i;
		}
	}
	printf("%d\n", ans);
	return 0;
}

int factorial(int n) {
	if (n > 0) {
		return n * factorial(n - 1);
	}
	else {
		return 1;
	}
}
int sum(int n, int *all) {
	int total = 0;
	for (int i = 0; i < n; ++i) {
		total += all[i];
	}
	return total;
}
int ave(int n, int *all) {
	int total = 0;
	for (int i = 0; i<n; ++i) {
		total += all[i];
	}
	return total / n;
}
int min(int n, int *all) {

	int min = all[0];
	for (int i = 1; i < n; ++i) {
		if (all[0] > all[i]) {
			min = all[i];
		}
	}
	return min;
}
int max(int n, int *all) {
	int max = all[0];
	for (int i = 1; i<n; ++i) {
		if (all[0]<all[i]) {
			max = all[i];
		}
	}
	return max;
}
int max(int n, int m) {
	if (n >= m) {
		return n;
	}
	else {
		return m;
	}
}
int min(int n, int m) {
	if (n >= m) {
		return m;
	}
	else {
		return n;
	}
}

Measured memory_bytes: 2656
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int MAX=500005;
const int INF=0x3f3f3f3f;
const int MOD=1000000007;
int n,ans[MAX],dx[4]={1,1,-1,-1},dy[4]={1,-1,1,-1};
char s[MAX];
int cl(){
    for(int i=0;i<n;i++) ans[i]=0;
}
int fans(int x){
    if(x==n){
        return (((ans[0]==1)==(s[0]=='o'))==(ans[n-1]==ans[1]))&&(((ans[n-1]==1)==(s[n-1]=='o'))==(ans[n-2]==ans[0]));
    }
    if((ans[x-1]==1)==(s[x-1]=='o')) ans[x]=ans[x-2];
    else ans[x]=-ans[x-2];
    return fans(x+1);
}
int main(){
    scanf(" %d %s",&n,s);
    for(int i=0;i<4;i++){
        cl();
        ans[0]=dx[i],ans[1]=dy[i];
        if(fans(2)){
            for(int i=0;i<n;i++) {
                if(ans[i]==1) printf("S");
                else printf("W");
            }
            printf("\n");
            return 0;
        }
    }
    printf("-1\n");
    return 0;
}


Measured memory_bytes: 896
#include <iostream>
#include <vector>
using namespace std;

struct UnionFind {
  vector<int> par;
  vector<int> sizes;

  UnionFind(int n) : par(n), sizes(n, 1) {
    for (int i = 0; i < n; i++) par[i] = i;
  }

  int find(int x) {
    return x == par[x] ? x : par[x] = find(par[x]);
  }

  void unite(int x, int y) {
    x = find(x);
    y = find(y);

    if (x == y) return;

    if (sizes[x] > sizes[y]) swap(x, y);

    par[x] = y;
    sizes[y] += sizes[x];
  }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N, M; cin >> N >> M;
    UnionFind uf(N);
    for (int i = 0; i < M; i++) {
        int X, Y, Z; cin >> X >> Y >> Z;
        uf.unite(X-1, Y-1);
    }
    int ans = 0;
    for (int i = 0; i < N; i++)
        if (uf.find(i) == i) ans++;
    cout << ans << "\n";
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl "\n"

int main()
{
  i64 N;
  cin >> N;
  vector<i64> A(N + 1);
  for (i64 i = 0; i <= N; i++)
    cin >> A[i];
  vector<i64> sum = A;
  for (i64 i = N; 0 < i; i--)
    sum[i - 1] += sum[i];
  i64 ans = 0, node = 1;
  for (i64 i = 0; i < N; i++)
  {
    ans += node;
    if (node - A[i] < 0)
    {
      cout << -1 << endl;
      return 0;
    }
    node = min((node - A[i]) * 2, sum[i + 1]);
  }
  ans += node;
  if (node - A[N] == 0)
    cout << ans << endl;
  else
    cout << -1 << endl;
  return 0;
}


Measured memory_bytes: 4764
//CLMN
//Every cloud has a silver lining
//Hakuna matata

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> ii;

#define fi first
#define se second
#define pb push_back
#define sqr(x) ((x) * (x))

const char *fin = "arc077_b.inp";
const char *fon = "arc077_b.out";

#define oo (int) (1e9+7)
#define maxn (int) (1e5+5)

int n, A, B;
int a[maxn], pos[maxn];
long long fact[maxn], inverse[maxn];

int getbit(int x, int y) {
    return (x >> y) & 1;
}

long long power(long long a, int b) {
    long long res = 1;
    while (b) {
        if (b & 1) res = (res * a) % oo;
        a = (a * a) % oo;
        b /= 2;
    }
    return res;
}

long long C(int n, int k) {
    if (k > n) return 0;
    long long tmp = (inverse[k] * inverse[n - k]) % oo;
    return (fact[n] * tmp) % oo;
}

void sol() {
    fact[0] = inverse[0] = 1;
    for(int i = 1; i <= n + 1; ++i) {
        fact[i] = (fact[i - 1] * i) % oo;
        inverse[i] = power(fact[i], oo - 2);
    }

    for(int l = 1; l <= n + 1; ++l) {
        long long res = C(n + 1, l);
        long long sub = C(A + B, l - 1);
        cout << (res - sub + oo) % oo << '\n';
    }
}

void inp() {
    //scanf("%d", &n);
    cin >> n;
    for(int i = 1; i <= n + 1; ++i) {
        //scanf("%d", a + i);
        cin >> a[i];
        if (pos[a[i]] != 0) B = n - i + 1, A = pos[a[i]] - 1;
        else pos[a[i]] = i;
    }
    sol();
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    //freopen(fin, "r", stdin); freopen(fon, "w", stdout);
    inp();
    return 0;
}


Measured memory_bytes: 3584
using System;
using System.Collections.Generic;
using System.Linq;

class Progaram
{
    static void Main(string[] args)
    {
        var n = Int32.Parse(Console.ReadLine());
        var x = new HashSet<String>();
        for (var i = 0; n > i; i++) x.Add(Console.ReadLine());
        Console.WriteLine(x.Count);
    }
}

Measured memory_bytes: 47284
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T,class U> using P = pair<T,U>;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;

int dp[1002][1002][2][2][2][2];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H,W;
    cin >> H >> W;
    vvec<int> F(H+2,vec<int>(W+2,0));
    for(int i=1;i<=H;i++) for(int j=1;j<=W;j++){
        char c;
        cin >> c;
        if(c!='.') F[i][j] = c-'0';
    }
    const int inf = 1e9;
    for(int i=0;i<=H;i++) for(int j=0;j<=W;j++){
        for(int a=0;a<2;a++) for(int b=0;b<2;b++) for(int c=0;c<2;c++) for(int d=0;d<2;d++) dp[i][j][a][b][c][d] = inf;
    }
    for(int a=0;a<2;a++) for(int b=0;b<2;b++) for(int c=0;c<2;c++) for(int d=0;d<2;d++) dp[1][1][a][b][c][d] = 0;
    for(int i=1;i<=H;i++) for(int j=1;j<=W;j++){
        for(int a=0;a<2;a++) for(int b=0;b<2;b++) for(int c=0;c<2;c++) for(int d=0;d<2;d++){
            //右に
            if(j<W){
                int p = (a? F[i][j+1]:0);
                //上を取らない
                dp[i][j+1][0][1][0][c] = min(dp[i][j+1][0][1][0][c],dp[i][j][a][b][c][d]+p+F[i][j+2]+F[i+1][j+1]);
                //右を取らない
                dp[i][j+1][1][1][0][c] = min(dp[i][j+1][1][1][0][c],dp[i][j][a][b][c][d]+p+(b? F[i-1][j+1]:0)+F[i+1][j+1]);
                //下を取らない
                dp[i][j+1][0][1][1][c] = min(dp[i][j+1][0][1][1][c],dp[i][j][a][b][c][d]+p+(b? F[i-1][j+1]:0)+F[i][j+2]);
            }
            if(i<H){
                int p = (c? F[i+1][j]:0);
                //左を取らない
                dp[i+1][j][0][a][0][1] = min(dp[i+1][j][0][a][0][1],dp[i][j][a][b][c][d]+p+F[i+2][j]+F[i+1][j+1]);
                //右を取らない
                dp[i+1][j][1][a][0][1] = min(dp[i+1][j][1][a][0][1],dp[i][j][a][b][c][d]+p+(d? F[i+1][j-1]:0)+F[i+2][j]);
                //下を取らない
                dp[i+1][j][0][a][1][1] = min(dp[i+1][j][0][a][1][1],dp[i][j][a][b][c][d]+p+(d? F[i+1][j-1]:0)+F[i+1][j+1]);
            }
        }
    }
    int ans = inf;
    for(int a=0;a<2;a++) for(int b=0;b<2;b++) for(int c=0;c<2;c++) for(int d=0;d<2;d++) ans = min(ans,dp[H][W][a][b][c][d]);
    cout << ans << endl;
}



Measured memory_bytes: 69600
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
#define rep(begin, i, end) for (ll i = begin; i < (ll)(end); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1000000007;

struct UnionFind
{
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N)
    { //最初は全てが根であるとして初期化
        for (int i = 0; i < N; i++)
            par[i] = i;
    }

    int root(int x)
    { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x)
            return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y)
    {                     // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry)
            return;   //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y)
    { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main()
{
    int N, M;
    cin >> N >> M;
    UnionFind tree(N);

    rep(0, i, M)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        tree.unite(a, b);
    }

    map<int, int> m;
    rep(0, i, N)
    {
        m[tree.root(i)]++;
    }

    ll ans = m.size() - 1;

    cout << ans << endl;
}

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

int main()
{ 
  int h, w ;
  cin >> h >> w ;
  vector<std::string> data ;
  for(int i = 0 ; i < h ; i++)
  {
    std::string str ;
    cin >> str ;
    for(int j = 0 ; j < w ; j++)
    {
      if(str.at(j) == '#')
      {
        data.push_back(str) ;
        break ;
      }
    }
  }

  vector<int> answer ;
  for(int i = 0 ; i < w ; i++)
  {
    for(int j = 0 ; j < data.size() ; j++)
    {
      if(data.at(j).at(i) == '#')
      {
        answer.push_back(i) ;
        break ;
      }
    }
  }

  for(int i = 0 ; i < data.size() ; i++)
  {
    for(int j = 0 ; j <= answer.size() ; j++)
    {
      if(j == answer.size())
      {
        cout << endl ;
        break ;
      }
      cout << data.at(i).at( answer.at(j) ) ;
    }
  }
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		String str[] = br.readLine().split("");

		int ans = 0;

		for (int i = 0; i <= 9; i++) {
			for (int j = 0; j <= 9; j++) {
				for (int k = 0; k <= 9; k++) {
					boolean flag1 = false;
					boolean flag2 = false;
					boolean flag3 = false;

					for (int l = 0; l < str.length; l++) {
						int num = Integer.parseInt(str[l]);
						if (num == k && flag2) {
							flag3 = true;
						} else if (num == j && flag1) {
							flag2 = true;
						} else if (num == i) {
							flag1 = true;
						}
					}

					if (flag1 && flag2 && flag3) {
						ans++;
					}
				}
			}
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 25424
#pragma GCC optimize("O3")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld  double
#define pii pair<int,int>
#define pip pair<int,pii>
#define ppi pair<pii,int> 
#define ppp pair<pii,pii>
#define pb push_back
#define N 200003
#define inf (ll)1e9+11
#define warmup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int mod=1e9+7;

signed main()
{
    warmup
    
    ll n,a,b,cnt;
    cin>>n>>a>>b;
    cnt=a*(n/(a+b));
    n-=(a+b)*(n/(a+b));
    cnt+=min(a,n);
    cout<<cnt;
    
    return 0;
}


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

using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define reps(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define allsort(v) sort(v.begin(),v.end())
const ll mod = 1e9 + 7;
const int inf = 1e9;

int main() {
	cin.sync_with_stdio(false);
	ll x, y;
	cin >> x >> y;
	int ans;
	if (abs(x) <= abs(y)) {
		ans = (x < 0 ? 1 : 0) + (y < 0 ? 1 : 0) + abs(y) - abs(x);
	}
	else {
		ans = (x > 0 ? 1 : 0) + (y > 0 ? 1 : 0) + abs(x) - abs(y);
	}
	cout << ans << endl;
	return 0;
}

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

int main() {

	int N;
	cin >> N;

	vector<int> L(N, 0);

	for (int i = 0; i < N; i++) {
		cin >> L[i];
	}

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

	int k = 0;
	long long cnt = 0;
	for (int i = 0; i < N - 2; i++) {
		for (int j = i + 1; j < N - 1; j++) {
			k = j + 1;
			while (L[i] + L[j] > L[k]) {
				cnt += 1;
				k += 1;
				if (k >= N) {
					break;
				}
			}
		}
	}

	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second
#define int long long
#define ull  unsigned long long
#define pb push_back

using namespace std;
using namespace __gnu_pbds;
typedef  tree< int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N = 120000;
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt",  "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n, m;
    cin >> n >> m;
    int s = 1900 * m + (n - m) * 100;
    int c = (1 << m);
    cout << s * c;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <stdio.h>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cfloat>
#include <math.h>
#include <stack>
#include <queue>
#include <cstdio>
#include <iomanip>

using namespace std;

#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++)
// #define req(j, n) for (ll j = 1; j < (n+1); j++)
// #define rer(k, n) for (ll k = 1; k < (n+1); k++)


// c問題
int main()
{
    int h, w, k;
    cin >> h >> w >> k;
    vector<string> s(h);
    rep(i,h) cin >> s[i];
    int ans = 0;
    rep(is,1<<h)rep(js,1<<w) {
        int cnt = 0;
        rep(i,h)rep(j,w) {
            if (is>>i&1) continue;
            if (js>>j&1) continue;
            if (s[i][j] == '#') cnt++;
        }
        if (cnt == k) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
#include<iomanip>
#define mins(a,b) a=min(a,b)
#define maxs(a,b) a=max(a,b)
template < typename T > std::string to_string( const T& n )
  {
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
  }
using namespace std;

const long long INF=9000000000000000;
const long long mod=1000000007;
typedef long long ll;

int main(){
  int a,b,c;
  cin>>a;
  if(a<100){
    cout<<min(9,a)<<endl;
  }
  else if(a>=100 and a<10000){
    cout<<9+min(900,a-99)<<endl;
  }
  else if(a>=10000){
    cout<<909+min(90000,a-9999)<<endl;
  }
}


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



const int N = 3e3 + 7;
string s, t;

int dp[N][N];
pair<int, int> construct[N][N];


int solve(int i, int j) {
	if (i == s.size() || j == t.size()) {
		return 0;
	}
	if (dp[i][j] != -1)
		return dp[i][j];

	if (s[i] == t[j]) {
		construct[i][j] = { i + 1, j + 1 };
		return dp[i][j] = 1 + solve(i + 1, j + 1);
	}
	else {
		int moveI = solve(i + 1, j);
		int moveJ = solve(i, j + 1);
		if (moveI > moveJ) {
			construct[i][j] = { i + 1, j };
		}
		else {
			construct[i][j] = { i, j + 1 };
		}
		return dp[i][j] = max(moveI, moveJ);
	}
}





int main() {
	cin >> s >> t;
	memset(dp, -1, sizeof dp);
	solve(0, 0);
	pair<int, int> curr = { 0, 0 };
	string ans = "";
	while (curr.first < s.size() && curr.second < t.size()) {
		if (s[curr.first] == t[curr.second]) {
			ans += s[curr.first];
		}
		curr = construct[curr.first][curr.second];
	}

	cout << ans;
}

Measured memory_bytes: 106752
A = []

for i in range(3):
    temp = list(map(int, input().rstrip().split(' ')))
    A.append(temp)

N = int(input())

bingo = [[0] * 3 for i in range(3)]
for i in range(N):
    b = int(input())
    for y, row in enumerate(A):
        try:
            pos = (y, row.index(b))
            break
        except ValueError:
            pass

    try:
        bingo[pos[0]][pos[1]] = 1
    except:
        pass

if bingo[0][0] == 1 and bingo[0][1] == 1 and bingo[0][2] == 1:
    print("Yes")
elif bingo[1][0] == 1 and bingo[1][1] == 1 and bingo[1][2] == 1:
    print("Yes")
elif bingo[2][0] == 1 and bingo[2][1] == 1 and bingo[2][2] == 1:
    print("Yes")
elif bingo[0][0] == 1 and bingo[1][0] == 1 and bingo[2][0] == 1:
    print("Yes")
elif bingo[0][1] == 1 and bingo[1][1] == 1 and bingo[2][1] == 1:
    print("Yes")
elif bingo[0][2] == 1 and bingo[1][2] == 1 and bingo[2][2] == 1:
    print("Yes")
elif bingo[0][0] == 1 and bingo[1][1] == 1 and bingo[2][2] == 1:
    print("Yes")
elif bingo[2][0] == 1 and bingo[1][1] == 1 and bingo[0][2] == 1:
    print("Yes")
else:
    print("No")






Measured memory_bytes: 38384
import heapq
import sys
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

def dijkstra(s,N,edge):
    d = [float('inf')] * N
    used = [False] * N
    d[s] = 0
    used[s] = True
    edgelist = []
    for w, i in edge[s]:
        heapq.heappush(edgelist, w * (10**6) + i)
        # (w * (10**6) + i) // 10 ** 6 => 距離 w　が求められる
        # (w * (10**6) + i) % 10 ** 6 => 頂点 i　が求められる
    
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge%(10**6)]:
            continue
        v = minedge % (10 ** 6)
        d[v] = minedge // (10 ** 6)
        used[v] = True
        for w, i in edge[v]:
            if not used[i]:
                heapq.heappush(edgelist,(w+d[v])*(10**6)+i)

    return d


def main():
    N  = int(input())
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append((w,v))
        edge[v].append((w,u))

    d = dijkstra(0,N,edge)

    for i in range(N):
        if d[i] % 2 == 0:
            print(0)
        else:
            print(1)


if __name__ == "__main__":
    main()

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

#define rep(i, N) for (int i = 0; i < (int)N; i++)
using namespace std;
typedef long long ll;
const ll LLINF = 9223372036854775807;
const int INF = pow(2,29);
const int MOD = 1000000007;

int main() {
  int t[3]; cin >> t[0] >> t[1] >> t[2];
  sort(t,t+3);
  int result = t[0] + t[1];
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, K;
    cin >> N >> K;
    
    int cnt[110] = {};
    rep(i, K) {
        int d; cin >> d;
        rep(j, d) {
            int a; cin >> a;
            a--;
            cnt[a]++;
        }
    }
    int ans = 0;
    rep(i, N) if(cnt[i] == 0) ans++;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3652
package main

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

func solve(w io.Writer, r io.Reader) {
	var A, B, C int
	fmt.Fscan(r, &A, &B, &C)

	if A < B && A < C && C < B || A > B && A > C && C > B {
		fmt.Fprintln(w, "Yes")
	} else {
		fmt.Fprintln(w, "No")
	}
}

func main() {
	solve(os.Stdout, os.Stdin)
}


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

int main(){
  ll H, A, ans;
  cin >> H >> A;
  ans = H/A;
  if(H%A){
    ans++;
  }

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

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

using namespace std;

typedef long long ll;
typedef pair< ll, ll > pll;

const double pi = 3.14159265358979323846;

#define MOD 1000000007LL
#define PS(p) cout << setprecision(15) << fixed << p << endl;
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
#define ALL(c) c.begin(), c.end()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define F first
#define S second
#define vl vector< ll >

// -----------------------------------------------------------------------------
// main
// -----------------------------------------------------------------------------
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  string s;
  cin >> s;

  for (auto c : s) {
    if (c == '9') {
      cout << 1;
    } else {
      cout << 9;
    }
  }

  cout << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define COUT(x) cout<<(x)<<endl
template<class T> inline void chmax(T& a, T b) {
  if (a < b) a = b;
}

template<class T> inline void chmin(T& a, T b) {
  if (a > b) a = b;
}

const long long INF = 1LL << 60;
int main() {
  int n;
  cin >> n;
  long long tmp = 0;
  long long ans = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      for (int k = 1; k <= n; ++k) {
        tmp = gcd(i, j);
        ans += gcd(tmp, k);
      }
    }
  }
  COUT(ans);
  return 0;

}

Measured memory_bytes: 3636
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

struct Pair {
  std::size_t b;
  std::size_t c;
};

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

  std::vector<std::size_t> a(n);
  for (auto&& ai : a) std::cin >> ai;
  std::sort(a.begin(), a.end());

  std::vector<Pair> pairs(m);
  for (auto&& p : pairs) std::cin >> p.b >> p.c;
  std::sort(pairs.begin(), pairs.end(),
            [](const auto& p1, const auto& p2) { return p1.c > p2.c; });

  std::size_t k = 0;
  for (auto&& p : pairs) {
    for (std::size_t j = 0; j < p.b; ++j) {
      if (a[k] < p.c)
        a[k++] = p.c;
      else
        break;
    }
  }

  const auto sum = std::accumulate(a.begin(), a.end(), 0ULL);
  std::cout << sum << std::endl;
}


Measured memory_bytes: 2560
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static final void main(String args[]) throws Exception {
        new Main().solve();
    }

    void solve() {
        try (Scanner in = new Scanner(System.in)) {
            int n = in.nextInt();
            long a[] = new long[n * 3];
            for (int i = 0; i < n * 3; ++i) {
                a[i] = in.nextLong();
            }
            Arrays.sort(a);
            long x = 0;
            for (int i = 0; i < n; ++i) {
                x += a[n * 3 - 2 - (2 * i)];
            }
            System.out.println(x);
        }
    }

    void tr(Object... o) {
        System.err.println(Arrays.deepToString(o));
    }
}

Measured memory_bytes: 97364
#include <iostream>
#include <algorithm>
#include<functional>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
int main() {
	int N, M;
	long long dp[100020] = {0};
	cin >> N >> M;
	for (int i = 0; i < 100020; i++) {
		dp[i] = 1;
	}

	for (int i = 0; i < M; i++) {
		int a;
		cin >> a;
		dp[a] = 0;
	}

	if (N == 1) {
		cout << dp[1];
	}
	else {
		for (int i = 2; i < N + 1; i++) {
			if (dp[i] == 0) {
				dp[i] = 0;
			}
			else {
				dp[i] = dp[i - 1] + dp[i - 2];
				dp[i] %= 1000000007;
			}
		}
		cout << dp[N];
	}
}

Measured memory_bytes: 1024
using System;

namespace DefaultNamespace
{
	/// <summary>
	/// Description of Class1.
	/// </summary>
	public class Class1
	{		
		public static void Main(String[] args)
		{
			
			int n = int.Parse(Console.ReadLine());
			
			var listA=new listArray();
			
			for(int i=0;i<n;i++)
			{
				string com=Console.ReadLine();
				string[] command=com.Split();
				switch (command[0])
				{
					case "insert":
						listA.insert(int.Parse(command[1]));
						//list[first]=int.Parse(command[1]);//first?????¨????????????first-1????????????????????\??£?????????
			//first++;
						break;
					case"deleteFirst":
						listA.deleteFirst();
						//first--;
						break;
					case"deleteLast":
						listA.deleteLast();
						//last++;				
						break;
					case "delete":
						listA.delete(int.Parse(command[1]));
						/*for(int j=first-1;j>=last;j--)
			{
							if(list[j]==command[1])
				{
					list[j]=-1;//?????????????????????-1???????????????
					break;
				}
			}
						*/
						break;				
				}
			}
			listA.finish();
		}			
	}


	public class listArray
	{
		public int first=0;
		public int last=0;
		public int[] list=new int[1000000];
		
		public void insert(int val)
		{
			list[first]=val;//first?????¨????????????first-1????????????????????\??£?????????
			first++;
		}
		public void deleteFirst()
		{
			first--;
			while(list[first-1]==-1)
			{
				first--;
			}
		}
		public void deleteLast()//last???????????\??£????????????
		{
			last++;
			while(list[last]==-1)
			{
				last++;
			}
		}
		public void delete(int val)
		{
			for(int j=first-1;j>=last;j--)
			{
				if(list[j]==val)
				{
					list[j]=-1;//?????????????????????-1???????????????
					while(list[first-1]==-1)
					{
						first--;
					}
					while(list[last]==-1)
					{
						last++;
					}
					return;
				}
			}
			return;
		}
		public void finish()
		{
				for(int k=first-1;k>last;k--)
			{
				if(list[k]!=-1)
				{
					Console.Write(list[k]+" ");
				}				
			}			
				Console.WriteLine(list[last]);	
		}	
	}	
}

Measured memory_bytes: 16464
#include "bits/stdc++.h"
using namespace std;
 
int MOD = 1000 * 1000 * 1000 + 7;
 
int main() {
	
	long long n;
	cin >> n;
	
	long long arr[62];
	memset(arr, 0, sizeof arr);
	for (int X=0; X<n; X++) {
		long long x;
		cin >> x;
		for (long long i=0; i<62; i++) {
			if (x & (1ll << i)) arr[i]++;
		}
	}
	
	long long p2[62];
	p2[0] = 1;
	for (int i=1; i<62; i++) {
		p2[i] = p2[i-1] * 2ll;
		p2[i] = p2[i] % MOD;
	}
	
	long long sm = 0;
	for (int i=0; i<62; i++) {
		// cout << arr[i] << ' ' << n-arr[i] << endl;
		long long su = ((long long) (arr[i])) * ((long long) (n - arr[i]));
		su = su % MOD;
		su = su * p2[i];
		su = su % MOD;
		sm += su;
		sm = sm % MOD;
	}
	cout << sm << endl;
	
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#define LEN 100005
typedef struct pp{
  char name[100];
  int t;
}P;
P Q[LEN+1];
int head,tail,n;
void enqueue(P x){
  Q[tail]=x;
  if(tail+1==LEN){
    tail=0;
  }
  else tail++;
}
P dequeue(){
  P x;
  x=Q[head];
  if(head+1==LEN)head=0;
  else head++;
  return x;
}
int main(){
  P u;
  int i,n,q,total_time=0;
  scanf("%d%d",&n,&q);
  for(i=0;i<n;i++){
  scanf("%s",u.name);
  scanf("%d",&u.t);
  enqueue(u);
  }
  
  while(head!=tail){
    u=dequeue();
    if(u.t>q){
      u.t=u.t-q;
      enqueue(u);
      total_time+=q;
    }
    else{
      printf("%s %d\n",u.name,u.t+total_time);
      total_time+=u.t;
    }
  }
  return 0;
}

Measured memory_bytes: 10756
#include<bits/stdc++.h>
#define int long long
using namespace std;

int gcd(int a, int b) {
	if (a < b)swap(a, b);
	int r;
	while (b != 0) {
		r = a % b;
		a = b;
		b = r;
	}
	return a;
}

signed main() {
	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	for (int i = 0; i < n; ++i)cin >> a[i];
	for (int& x : a) {
		if (x % 2 == 1) {
			cout << 0 << endl;
			return 0;
		}
		else x /= 2;
	}
	int cnt = 1;
	for (int& x : a) {
		cnt = cnt * x / gcd(cnt, x);
	}
	int beki = 0;
	while (cnt % (int)std::pow(2, beki + 1) == 0)beki++;
	for (int x : a) {
		if (x % (int)std::pow(2, beki) == 0 && x % (int)pow(2, beki + 1) != 0);
		else {
			cout << 0 << endl;
			return 0;
		}
	}
	int ans = m / cnt;
	cout << (ans % 2 == 0 ? ans / 2 : ans / 2 + 1) << endl;
}

Measured memory_bytes: 1024