AtCoder 183

A - ReLU

relu.cppview raw

#include <iostream>
using namespace std;

int main(){
    int x;
    cin>>x;
    x = max(x, 0);
    cout<<x<<endl;
    return 0;
}

B - Billiards
Ouput the turning point given input point and output point.

billards.cppview raw

#include <iostream>
using namespace std;

int main(){
    double sx, sy, gx, gy;
    cin>>sx>>sy>>gx>>gy;
    double x = (double)(sy*gx + sx * gy) / (sy+gy);
    printf("%.10lf\n", x);
    return 0;
}

C - Travel
Find the number of paths from city 1 to city n with total distance equalling to k.

travel.cppview raw

#include <iostream>
using namespace std;

const int  N = 10;
int g[N][N];
bool vis[N];
int n, k;

int res = 0;

void dfs(int u, int cnt, int dis){
    if(cnt==n){
        dis += g[u][1];
        if(dis==k) res++;
        return;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            vis[i] = 1;
            dfs(i, cnt+1, dis + g[u][i]);
            vis[i] = 0;
        }
    }
}

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>g[i][j];
    vis[1] = 1;
    dfs(1, 1, 0);
    cout<<res<<endl;
    return 0;
}

D - Water Heater
A water heater is able to provide W liters at a given minute.
There are N people, the i-th people needs P_i water from S_i to E_i.
Is it possible to satisfy everyone?

water-heater.cppview raw

//差分数组， 或者扫描线
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 200010;
typedef long long LL;
LL b[N];
int n, w;

int main(){
    cin>>n>>w;
    for(int i=0;i<n;i++) {
        int st, ed, c;
        scanf("%d%d%d", &st, &ed, &c);
        b[st] += c, b[ed] -= c;
    }
    for(int i=1;i<n;i++) b[i] += b[i-1];
    bool flag = true;
    for(int i=0;i<n;i++) if(b[i] > w){
        flag = false;
        break;
    }
    if(flag) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

E - Queen on Grid
The number of ways from (1,1) to (H, W). Need to take care of walls in the path.

queen-grid.cppview raw

#include <iostream>
using namespace std;

const int N = 2010;
char g[N][N];

typedef long long LL;
int f[N][N], rsum[N][N], csum[N][N], dsum[N][N];
int n, m;
const int mod = 1e9 + 7;

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        scanf("%s", g[i]);

    f[1][1] = 1;
    rsum[1][1] = 1, csum[1][1] = 1, dsum[1][1] = 1;
    for(int i=1;i<=n;i++) {
        for (int j = 1; j <= m; j++) {
            if (g[i - 1][j - 1] == '#') {
                f[i][j] = 0;
                rsum[i][j] = 0, csum[i][j] = 0, dsum[i][j] = 0;
                continue;
            }
            LL tmp = f[i][j];
            tmp = (tmp + rsum[i-1][j]) % mod;
            tmp = (tmp + csum[i][j-1]) % mod;
            tmp = (tmp + dsum[i-1][j-1]) % mod;

            f[i][j] = tmp;
            rsum[i][j] = (rsum[i-1][j] + f[i][j]) % mod;
            csum[i][j] = (csum[i][j-1] + f[i][j]) % mod;
            dsum[i][j] = (dsum[i-1][j-1] + f[i][j]) % mod;
        }
    }

//    for(int i=1;i<=n;i++){
//        for(int j=1;j<=m;j++)
//            printf("%d ", f[i][j]);
//        puts("");
//    }

    cout<<f[n][m]<<endl;
    return 0;
}

F - Confluence
N students belonging to C different classes.
1 a b: join student a and b in the same group
2 a b: query the number of students belonging to class b from group of student a;

confluence.cppview raw

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

int n, q;
const int N = 200010;
int p[N];

int find(int x){
    if(p[x]!=x) p[x] = find(p[x]);
    return p[x];
}

int main(){
    cin>>n>>q;
    vector<map<int,int>> cnt(n+1);
    for(int i=1;i<=n;i++) {
        int c;
        scanf("%d", &c);
        p[i] = i;
        cnt[i][c] = 1;
    }

    while(q--){
        int x, a, b;
        scanf("%d%d%d", &x, &a, &b);
        if(x==1){
            int fa = find(a), fb = find(b);
            if(fa!=fb){
                if(cnt[fa].size() > cnt[fb].size()) swap(fa, fb);
                p[fa] = fb;
                for(auto [k,v]: cnt[fa]) cnt[fb][k] += v;
            }
        }else{
            int fa = find(a);
            printf("%d\n", cnt[fa][b]);
        }
    }
    return 0;
}