TJ-S00715

:::info[T1]

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

const int N=5e5+10;
typedef long long ll;
ll n,m;
ll a[N],sum[N];

bool check(int xx){
    ll cnt=0x7f7f7f7f7f7f7f7f;
    for(int i=1;i+xx-1<=n;i++){
        int j=i+xx-1;
        cnt=min(cnt,xx*a[j]-(sum[j]-sum[i-1]));
    }
    return cnt<=m;
}
int main(){
    freopen("crystal.in","r",stdin);
    freopen("crystal.out","w",stdout);

    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];

    int l=1,r=n;
    while(l<=r){
        int mid=l+((r-l)>>1);
        if(check(mid)) l=mid+1;
        else r=mid-1;
    }
    cout<<r;
    return 0;
} 

:::

:::info[T2]

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

typedef long long ll;
//typedef pair<long long,int> PII
const int N=5e5+10,M=510;
int num,n,m,d,q,w[M];
int t[N][M];
struct edge{
    int to,id;
};
vector<edge> a[M];
int idx[M];
ll dis[M];
bool f[M];
bool lijie[M];
int yaojia;
//priority_queue<PII, vector<PII>, greater<PII> > q;

void dijstra(int s){
    memset(dis,0x3f,sizeof(dis));

    bool lijieflag=1;
    dis[s]=0;
    for(int i=1;i<=m;i++){
        int mi=0;
        for(int j=1;j<=m;j++)
            if(!f[j] && dis[j]<=dis[mi]) mi=j;
        //cout<<mi<<' ';

        f[mi]=1;
        //cout<<mi<<':';
        if(lijie[mi] && lijieflag) {
            yaojia=idx[mi];
            lijieflag=0;
        }
        for(int j=0;j<a[mi].size();j++){
            int to=a[mi][j].to, id=a[mi][j].id;
            //cout<<to<<' ';
            if(mi==s) {
                //cout<<1;
                if(dis[mi]<dis[to]) {
                    dis[to]=dis[mi];
                    idx[to]=id;
                    lijie[to]=1;
                }
            }else { 
                if(id==idx[mi] && dis[mi]<dis[to]){
                    //cout<<2;
                    dis[to]=dis[mi];
                    idx[to]=id;
                    //cout<<dis[to];
                } else {
                    //cout<<3;
                    ll l=t[idx[mi]][mi]+t[id][mi];
                    //if(to==3) cout<<l;
                    if(dis[mi]+l<dis[to]){
                        dis[to]=dis[mi]+l;
                        idx[to]=id;
                    }
                }
            } 
            //ut<<dis[to]<<' ';
        }
        //cout<<dis[s];
        //cout<<"\n";
    }
}
int main(){
    freopen("subway.in","r",stdin);
    freopen("subway.out","w",stdout);

    cin>>num>>n>>m>>d>>q;
    for(int i=1;i<=m;i++) cin>>w[i];
    for(int i=1;i<=n;i++){
        int k;
        cin>>k;

        int from;
        cin>>from;
        cin>>t[i][from];
        for(int j=2;j<=k;j++){
            int to;
            cin>>to;
            cin>>t[i][to];
            a[from].push_back({to,i});
            from=to;
        }
    }


    /*for(int i=1;i<=m;i++){
        for(int j=0;j<a[i].size();j++){
            cout<<a[i][j].to<<" ";
        }
        cout<<'\n';
    }*/
    dijstra(1);
    //for(int i=1;i<=m;i++) cout<<dis[i]<<' ';
    //cout<<endl;
    while(q--){
        int s,e;
        cin>>s>>e;
        yaojia=0;
        dijstra(s);
        cout<<w[s]+w[e]+dis[e]+t[yaojia][s]+t[idx[e]][e]<<'\n';
        //for(int i=1;i<=m;i++) cout<<dis[i]<<' ';
        //cout<<endl;
    }
    return 0;
}

:::

:::info[T3]

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

using ll = long long;

int main() {

    freopen("migrate.in", "r", stdin);
    freopen("migrate.out", "w", stdout);

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

    int c, T;
    if (!(cin >> c >> T)) return 0;
    while (T--) {
        int n;
        ll d;
        cin >> n >> d;
        vector<ll> x(n + 1);
        for (int i = 1; i <= n; ++i) cin >> x[i];

        vector<int> reach(n + 1), left(n + 1);
        int r = 1;
        for (int i = 1; i <= n; ++i) {
            if (r < i) r = i;
            while (r + 1 <= n && x[r + 1] - x[i] <= d) ++r;
            reach[i] = r;
        }
        int l = 1;
        for (int i = 1; i <= n; ++i) {
            while (x[i] - x[l] > d) ++l;
            left[i] = l;
        }

        long long ans = 0;
        vector<unsigned char> ways(n + 1);
        vector<int> pref(n + 1);

        for (int s = 1; s < n; ++s) {
            if (reach[s] == s) continue;
            fill(ways.begin() + s, ways.begin() + reach[s] + 1, 0);
            ways[s] = 1;
            int layerL = s, layerR = s;
            while (layerR < n) {
                int nextR = reach[layerR];
                if (nextR <= layerR) break;

                pref[layerL - 1] = 0;
                for (int i = layerL; i <= layerR; ++i)
                    pref[i] = pref[i - 1] + (int)ways[i];
                int total = pref[layerR];

                int nextL = layerR + 1;
                for (int v = nextL; v <= nextR; ++v) {
                    int p = max(layerL, left[v]);
                    int cnt = total - pref[p - 1];
                    ways[v] = (unsigned char)min(cnt, 3);
                    if (ways[v] == 2) ++ans;
                }

                layerL = nextL;
                layerR = nextR;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

:::

:::info[T4]

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int INF = 1e9;

int n, k;
vector<int> g[N];
int fa[N], dep[N];
bool vis[N];
int cnt;

void dfs1(int u, int p, int d) {
    fa[u] = p;
    dep[u] = d;
    for (int v : g[u]) {
        if (v != p) dfs1(v, u, d + 1);
    }
}

void cover(int u, int p, int r) {
    vis[u] = true;
    if (r == 0) return;
    for (int v : g[u]) {
        if (v != p) cover(v, u, r - 1);
    }
}

bool check(int R) {
    for (int i = 1; i <= n; i++) vis[i] = false;
    cnt = 0;
    while (1) {
        int u = -1, mx = -1;
        for (int i = 1; i <= n; i++) {
            if (!vis[i] && dep[i] > mx) {
                mx = dep[i];
                u = i;
            }
        }
        if (u == -1) break;
        int c = u;
        for (int i = 0; i < R && fa[c] != 0; i++) c = fa[c];
        cover(c, 0, R);
        cnt++;
        if (cnt > 2) return false;
    }
    return cnt <= 2;
}

int d[15][15];

void bfs(int s) {
    for (int i = 1; i <= n; i++) d[s][i] = INF;
    d[s][s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) {
            if (d[s][v] == INF) {
                d[s][v] = d[s][u] + 1;
                q.push(v);
            }
        }
    }
}

int solve() {
    for (int i = 1; i <= n; i++) bfs(i);
    int ans = INF;
    for (int mask = 0; mask < (1 << n); mask++) {
        if (__builtin_popcount(mask) != k) continue;
        vector<int> a;
        for (int i = 1; i <= n; i++) {
            if (mask >> (i - 1) & 1) a.push_back(i);
        }
        int e = 0;
        for (int u : a) {
            for (int v : g[u]) {
                if ((mask >> (v - 1) & 1) && u < v) e++;
            }
        }
        if (k - e > 2) continue;
        int r = 0;
        for (int i = 1; i <= n; i++) {
            int mn = INF;
            for (int j : a) mn = min(mn, d[i][j]);
            r = max(r, mn);
        }
        ans = min(ans, r);
    }
    return ans;
}

int main() {
    freopen("hub.in","r",stdin);
    freopen("hub.out","w",stdout);
    int c, t;
    scanf("%d %d", &c, &t);
    while (t--) {
        scanf("%d %d", &n, &k);
        for (int i = 1; i <= n; i++) g[i].clear();
        for (int i = 0; i < n - 1; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        if (n <= 10) {
            printf("%d\n", solve());
        } else if (k == 2) {
            dfs1(1, 0, 0);
            int l = 0, r = n;
            while (l < r) {
                int mid = (l + r) / 2;
                if (check(mid)) r = mid;
                else l = mid + 1;
            }
            printf("%d\n", l);
        } else {
            printf("0\n");
        }
    }
    return 0;
}

:::