Codeforces Round #816 (Div. 2)

#include<stdio.h>
#include<algorithm>
 
int T,n,m;
 
int main() {
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d",&n,&m);
        if (n<m) std::swap(n,m);
        if (n==1) puts("0");
        else printf("%d\n",n+(m-1<<1));
    }
    return 0;
}

#include<stdio.h>
#define int long long
 
int T,n,k,b,s,x;
 
signed main() {
    scanf("%lld",&T);
    while (T--) {
        scanf("%lld%lld%lld%lld",&n,&k,&b,&s);
        if ((s-=k*b)<0) { puts("-1"); continue; }
        if ((k-1)*n<s) { puts("-1"); continue; }
        for (int i=1; i<n; ++i)
            x=(s>=k-1?k-1:s),
            printf("%lld ",x),s-=x;
        printf("%lld\n",k*b+s);
    }
    return 0;
}

#include<stdio.h>
typedef long long ll;
 
const int N=1e5+5;
 
int n,m,i,x,a[N]; ll ans;
 
void upd(int i,int x) {
    ll d1=(x!=a[i-1])-(a[i]!=a[i-1]);
    ll d2=(x!=a[i+1])-(a[i]!=a[i+1]);
    ans+=d1*(i-1)*(n-i+1)+d2*i*(n-i);
    a[i]=x;
}
 
int main() {
    scanf("%d%d",&n,&m);
    ans=1ll*n*(n+1)>>1;
    for (int i=1; i<=n; ++i)
        scanf("%d",&x),upd(i,x);
    while (m--)
        scanf("%d%d",&i,&x),upd(i,x),
        printf("%lld\n",ans);
    return 0;
}

#include<stdio.h>
#include<ctype.h>
#include<string.h>
#define rep(i,l,r) for (int i=l; i<=r; ++i)
#define repE(i,x) for (int i=lst[x]; i; i=E[i].pre)

const int N=1e5+5,M=2e5+5;

int n,m,x,y,w,cnt;
int lst[N],ans[N],v[N];
struct Node { int x,y,w; }Q[M];
struct Edge { int y,pre; }E[M<<1];

inline int read() {
    int x=0; char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return x;
}

int main() {
    n=read(),m=read();
    rep(i,1,m) {
        x=read(),y=read(),w=read();
        Q[i]={x,y,w};
    }
    rep(k,0,29) {
        cnt=0;
        memset(lst,0,sizeof lst);
        memset(v,-1,sizeof v);
        rep(i,1,m) {
            x=Q[i].x,y=Q[i].y,w=(Q[i].w>>k)&1;
            if (w&&x!=y)
                E[++cnt]={y,lst[x]},lst[x]=cnt,
                E[++cnt]={x,lst[y]},lst[y]=cnt;
            else v[x]=v[y]=w;
        }
        rep(i,1,n) if (!v[i]) //已经填0
            repE(j,i) v[E[j].y]=1; //相邻点必须填1
        rep(i,1,n) {
            if (v[i]==1) {
                ans[i]|=(1<<k);
                continue;
            }
            v[i]=0;
            repE(j,i) v[E[j].y]=1;
        }
    }
    rep(i,1,n) printf("%d ",ans[i]);
    return 0;
}

#include<stdio.h>
#include<queue>
#define rep(i,l,r) for (int i=l; i<=r; ++i)
typedef long long ll;

const int N=1e5+5;

int n,m,k,x,y,w,cnt,lst[N]; ll d[N];

struct Edge { int y,w,pre; }E[N<<1];

struct Node { int x; ll dis; };
bool operator < (Node p,Node q) { return p.dis>q.dis; }
std::priority_queue<Node>Q;

struct Point { int x; ll y; }L[N];
bool cmp(Point a,Point b,Point c,Point d) { 
    return (a.y-b.y)*(c.x-d.x)>(c.y-d.y)*(a.x-b.x); //k(AB)>k(CD)
}

void dijkstra() {
    rep(i,1,n) Q.push({i,d[i]});
    while (!Q.empty()) {
        Node q=Q.top(); Q.pop();
        if (q.dis!=d[q.x]) continue;
        for (int i=lst[q.x],y; i; i=E[i].pre)
            if (d[y=E[i].y]>d[q.x]+E[i].w) {
                d[y]=d[q.x]+E[i].w;
                Q.push({y,d[y]});
            }
    }
}

void dp() {
    int l=1,r=0;
    rep(i,1,n) { //单调队列维护下凸壳
        Point t={i<<1,d[i]+1ll*i*i};
        while (l<r&&cmp(L[r-1],L[r],L[r],t)) --r;
        L[++r]=t;
    }
    rep(i,1,n) {
        Point t1={0,0},t2={1,i};
        while (l<r&&cmp(t1,t2,L[l],L[l+1])) ++l;
        d[i]=L[l].y-1ll*L[l].x*i+1ll*i*i;
    }
}

int main() {
    scanf("%d%d%d",&n,&m,&k);
    rep(i,1,m)
        scanf("%d%d%d",&x,&y,&w),
        E[++cnt]={y,w,lst[x]},lst[x]=cnt,
        E[++cnt]={x,w,lst[y]},lst[y]=cnt;
    rep(i,2,n) d[i]=1e11;
    while (k--) dijkstra(),dp();
    dijkstra();
    rep(i,1,n) printf("%lld ",d[i]);
    return 0;
}