Heuristics 22 Editorials

assigning-heroes.cpp

#include<bits/stdc++.h>
using namespace std;
typedef long long ulli;
#define int ulli
const int mod = 1e9+7;

struct Node{
    int ind,dist;
    vector<int> next;
    Node(){
        ind = -1;
        dist = INT_MAX;
    }
    void clear(){
        ind = -1;
        dist = INT_MAX;
        next.clear();
    }
}node[100009];

bool comp(int a,int b){
    return node[a].dist < node[b].dist;
}

void bfs(queue<int> &q){
    while(!q.empty()){
        int i = q.front();
        q.pop();
        for(auto a: node[i].next)
            if(node[a].dist > node[i].dist + 1){
                node[a].dist = node[i].dist + 1;
                q.push(a);
            }
    }
}


void preprocess(int n){
    for(int i=0;i<=n;i++)
        node[i].clear();
}

void solve(){
    int n,m,x,k;
    cin>>n>>m>>k>>x;
    preprocess(n);
    for(int i=0;i<m;i++) {
        int a,b;
        cin>>a>>b;
        node[a].next.push_back(b);
        node[b].next.push_back(a);
    }
    queue<int> q;
    for(int i=1;i<=x;i++) {
        int a;
        cin>>a;
        node[a].dist = 0;
        q.push(a);
    }
    bfs(q);

    vector<int> arr(n);
    for(int i=0;i<n;i++) arr[i] = i+1;
    sort(arr.begin(),arr.end(),comp);

    int ans = 0;
    for(int i=0;i<k;i++) ans += node[arr[i]].dist;
    cout << ans << endl;
}

signed main(){
    int t=1;
    cin>>t;
    while(t--)solve();
}

brackets-regularity.cpp

#include <bits/stdc++.h>
using namespace std;

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

	while(t--)
	{
		string s;
		cin>>s;
		int count=0,flag=0;

		for(int i=0;i<s.length(); i++)
		{
			if(s[i]=='(')
			{
				// flag=0;
				flag++;
			}
			else if(s[i]==')')
			{
				flag--;
			}
			if(flag<0)
			{
				break;
			}
			if(flag==0)
			{
				count++;
			}
		}

		if(flag==0)
			cout<<count<<endl;
		else
			cout<<0<<endl;
	}
}

easy-problem.cpp

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

int main() {
	int t;
	scanf("%d", &t);
	while(t--) {
		int a, b;
		cin >> a >> b;
		int g = __gcd(a, b);
		ll a1 = a, b1 = b, g1 = g;
		cout << (a1 * b1) / g1 << endl;
	}
	return 0;
}

make-em-one.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;


ll cnt[800100], tree[800100];
int a[200100];
ll ans[200100];
int n, qc;

void update(int l, ll val, int i=1, int cl=1, int cr=n) {
    if (l == cl && cl == cr) {
        cnt[i] = 1;
        tree[i] = val;
    }
    else {
        int mid = (cl + cr) / 2;
        if (l <= mid)
            update(l, val, 2*i, cl, mid);
        else
            update(l, val, 2*i+1, mid+1, cr);
        tree[i] = tree[2*i] + tree[2*i+1];
        cnt[i] = cnt[2*i] + cnt[2*i+1];
    }
}


pii get(int l, int r, int i=1, int cl=1, int cr=n) {
    if (cr < l || cl > r)
        return make_pair(0, 0);
    else if (l <= cl && cr <= r)
        return make_pair(tree[i], cnt[i]);
    else {
        int mid = (cl + cr) / 2;
        pii lft = get(l, r, 2*i, cl, mid);
        pii rgt = get(l, r, 2*i+1, mid+1, cr);
        return make_pair(lft.first + rgt.first, lft.second + rgt.second);
    }
}

struct query {
    int k, i, l, r;
} q[200100];

bool cmp(query &a, query &b) {
    return a.k < b.k;
}

vector<pii> p;
pii big[200100], small[200100];


int main(void) {
    scanf("%d %d", &n, &qc);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        p.push_back(make_pair(a[i], i));
    }
    for (int i = 1; i <= qc; i++) {
        scanf("%d %d %d", &q[i].l, &q[i].r, &q[i].k);
        q[i].i = i;
    }
    sort(q + 1, q + 1 + qc, cmp);
    sort(p.begin(), p.end());
    int j = 0;
    for (int i = 1; i <= qc; i++) {
        while (j < n && p[j].first < q[i].k) {
            update(p[j].second, p[j].first);
            j++;
        }
        small[q[i].i] = get(q[i].l, q[i].r);
    }
    j = n - 1;
    memset(tree, 0, sizeof(tree));
    memset(cnt, 0, sizeof(cnt));
    for (int i = qc; i >= 1; i--) {
        while (j >= 0 && p[j].first > q[i].k) {
            update(p[j].second, p[j].first);
            j--;
        }
        big[q[i].i] = get(q[i].l, q[i].r);
    }
    for (int i = 1; i <= qc; i++) {
        int k = q[i].k;
        int j = q[i].i;
        ll one = big[j].first - (k * big[j].second);
        ll two = (k * small[j].second) - small[j].first;
        ans[j] = one + two;
    }
    for (int i = 1; i <= qc; i++)
        printf("%lld\n", ans[i]);
    return 0;
}

math-love.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int siz = 1e6 + 10;
const ll modu = 1e9 + 7;
const int lim = 1e6;

int min_factor[siz];

int main() {
	int t;
	scanf("%d", &t);
	memset(min_factor, 0, sizeof(int) * siz);
	for(int i = 2; i < siz; i++)
		if(!min_factor[i]) { 
			for(int j = i; j < siz; j += i)
				if(!min_factor[j])
					min_factor[j] = i;
		}
	while(t--) {
		int a, b;
		scanf("%d%d", &a, &b);
		int ans = 0;
		while(b >= a) {
			int p = min_factor[b];
			b /= p;
			ans++;
		}
		printf("%d\n", ans);
	}
	return 0;
}