CSES Graph Algorithms

發表於 更新於 分類於 ， 閱讀次數： 文章字數： 1.1k 所需閱讀時間 ≈ 2 分鐘

CSES Graph Algorithms

CSES Graph Algorithms 的 AC 程式碼

CSES Problem Set

我的 Profile

我的程式們

Counting Rooms

Counting Rooms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define rep(i,a,b) for(int i = a; i<=b; i++)
#define rev(i,a,b) for(int i = a; i>=b; i--)
#define tomax(a,b) (a)=max(a,b)
#define tomin(a,b) (a)=min(a,b)
#define pb push_back
#define eb emplace_back
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

int n, m, room=0;
bool is_floor[1003][1003];

void dfs(int i, int j){
    if(!is_floor[i][j]) return;
    is_floor[i][j]=0;
    dfs(i+1,j), dfs(i-1,j), dfs(i,j+1), dfs(i,j-1);
}

signed main(){
    ios;
    cin >> n >> m;
    char tmp;
    memset(is_floor, 0, sizeof(is_floor));
    rep(i, 1, n)
        rep(j, 1, m)
            cin>>tmp, is_floor[i][j]=(tmp=='.');
    rep(i, 1, n)
        rep(j, 1, m)
            if(is_floor[i][j])
                room++, dfs(i, j);
    cout << room << '\n';
    return 0;
}

Labyrinth

Labyrinth
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define rep(i, a, b) for(int i = a; i<=b; ++i)
#define rev(i, a, b) for(int i = a; i>=b; --i)
#define tomax(a, b) (a)=max((a),(b))
#define tomin(a, b) (a)=min((a),(b))
#define all(a) a.begin(), a.end()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int n, m;
pii a, b;
bool find_path = false;
bool graph[1003][1003];
queue<pii> q;
vector<char> path;
int dir[1003][1003];

signed main(){
    ios;
    memset(graph, 0, sizeof(graph));
    cin >> n >> m;
    char tmp;
    rep(i, 1, n)
        rep(j, 1, m)
            cin >> tmp, graph[j][i]=(tmp!='#'&&tmp!='A'),
            a = (tmp=='A' ? make_pair(j,i) : a),
            b = (tmp=='B' ? make_pair(j,i) : b);
    q.push(a);
    while(q.size()){
        int x = q.front().F, y = q.front().S; q.pop();
        if(x==b.F && y==b.S){ find_path=true; break;}
        if(graph[x-1][y]) dir[x-1][y]='L', graph[x-1][y]=0, q.push({x-1, y});
        if(graph[x+1][y]) dir[x+1][y]='R', graph[x+1][y]=0, q.push({x+1, y});
        if(graph[x][y-1]) dir[x][y-1]='U', graph[x][y-1]=0, q.push({x, y-1});
        if(graph[x][y+1]) dir[x][y+1]='D', graph[x][y+1]=0, q.push({x, y+1});
    }
    if(!find_path){cout << "NO\n"; return 0;}
    while(a!=b){
        path.pb(dir[b.F][b.S]);
        if(dir[b.F][b.S]=='L') b={b.F+1, b.S};
        else if(dir[b.F][b.S]=='R') b={b.F-1, b.S};
        else if(dir[b.F][b.S]=='U') b={b.F, b.S+1};
        else if(dir[b.F][b.S]=='D') b={b.F, b.S-1};
    }reverse(all(path));
    cout << "YES\n" << path.size() << '\n';
    for(char i : path) cout << i;
    cout << '\n';
    return 0;
}

Building Roads

Building Roads
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define rep(i, a, b) for(int i = a; i<=b; ++i)
#define rev(i, a, b) for(int i = a; i>=b; --i)
#define tomax(a, b) (a)=max((a),(b))
#define tomin(a, b) (a)=min((a),(b))
#define all(a) a.begin(), a.end()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int bose[100005];

int fb(int ch){
    if(ch==bose[ch]) return ch;
    return bose[ch]=fb(bose[ch]);
}

signed main(){
    ios;
    // minimum spanning tree
    int n, m, connect=0;
    cin >> n >> m;
    vector<pii> E(m);
    for(pii &x : E) cin >> x.F >> x.S;
    rep(i, 1, n) bose[i]=i;
    for(pii path : E){
        if(connect==0 || fb(path.F) != fb(path.S))
            bose[fb(path.F)]=bose[fb(path.S)], connect++;
    }cout << n-1-connect << '\n';
    rep(i, 2, n){
        if(fb(i-1)!=fb(i))
            bose[fb(i-1)]=bose[fb(i)], cout << i-1 << ' ' << i << '\n';
    }
    return 0;
}

Message Route

Message Route
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int n, m, tmp1, tmp2;
int last_cpu[100005];
vector<int> E[100005];
vector<int> ans;

signed main() {
    ios;
    // BFS
    fill(last_cpu, last_cpu+100005, INT_MAX);
    cin >> n >> m;
    rep(i, 1, m) cin >> tmp1 >> tmp2, E[tmp1].eb(tmp2), E[tmp2].eb(tmp1);
    queue<int> q;
    q.push(1); last_cpu[1]=1;
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for(int x : E[cur])
            if(last_cpu[x]==INT_MAX) q.push(x), last_cpu[x]=cur;
    }
    if(last_cpu[n]!=INT_MAX){
        while(n!=1){
            ans.pb(n);
            n=last_cpu[n];
        }cout << ans.size()+1 << '\n';
        reverse(all(ans));
        cout << 1 << ' ';
        for(int x : ans) cout << x << ' ';
    }else{
        cout << "IMPOSSIBLE\n";
    }
    return 0;
}

Building Teams

Building Teams
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vi vector<int>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

vi E[100005];
vi team;
int n, m, tmp1, tmp2;
bool build_team = true;

void dfs(int r) {
    int draw = team[r] % 2 + 1;
    for (int i : E[r]) {
        if (team[i] == 0)
            team[i] = draw, dfs(i);
        else if (team[i] == draw)
            continue;
        else {
            build_team = false;
            return;
        }
    }
}

signed main() {
    ios;
    // bipartite graph
    cin >> n >> m;
    team.resize(n + 1), team.assign(n + 1, 0);
    rep(i, 1, m) {
        cin >> tmp1 >> tmp2;
        E[tmp1].eb(tmp2), E[tmp2].eb(tmp1);
    }
    rep(i, 1, n) {
        if (team[i] == 0) team[i] = 1, dfs(i);
    }
    if (build_team) {
        team.erase(team.begin());
        for (int i : team) cout << i << ' ';
    } else
        cout << "IMPOSSIBLE";
    return 0;
}

Round Trip

Round Trip
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vi vector<int>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, m, min_l = INT_MAX, min_ls, min_le;
vi E[100005];
int lev[100005], parent[100005];
bool vis[100005];

void dfs(int u) {
    if (vis[u]) return;
    vis[u] = 1;
    for (int i : E[u]) {
        if (!vis[i])
            lev[i] = lev[u] + 1, parent[i] = u, dfs(i);
        else if(lev[u] > lev[i] && i != parent[u]){
            int path = lev[u] - lev[i] + 2;
            if (path < min_l) min_l=path, min_ls = u, min_le = i;
        }
    }
}

signed main() {
    ios;
    int tmp1, tmp2;
    memset(vis, 0, sizeof(vis));
    memset(lev, 0, sizeof(lev));
    cin >> n >> m;
    rep(i, 1, m) cin >> tmp1 >> tmp2, E[tmp1].eb(tmp2), E[tmp2].eb(tmp1);
    rep(i, 1, n) dfs(i);
    if(min_l == INT_MAX) cout << "IMPOSSIBLE\n";
    else{
        cout << min_l << '\n';
        tmp1 = min_ls;
        rep(i, 2, min_l){
            cout << min_ls << ' ';
            min_ls = parent[min_ls];
        }cout << tmp1 << '\n';
    }
    return 0;
}

Monsters

Monsters
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
// #define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

bool vis[1003][1003];
bool vis_h[1003][1003];

signed main() {
    ios;
    int n, m;
    char g[1003][1003];
    cin >> n >> m;
    queue<pair<pii, bool> > pt;
    int from[1003][1003];
    bool ok = 0;
    pair<pii, bool> a;
    pii de;
    int dir_x[5] = {1, 0, -1, 0}, dir_y[5] = {0, 1, 0, -1};
    char dir[5] = {'D', 'R', 'U', 'L'};

    rep(i, 0, n - 1) rep(j, 0, m - 1) {
        cin >> g[i][j];
        if (g[i][j] == '#') vis[i][j] = 1;
        if (g[i][j] == 'M') pt.push({{i, j}, 0}), vis[i][j] = 1;
        if (g[i][j] == 'A') a = {{i, j}, 1}, vis_h[i][j] = 1;
    }
    pt.push(a);
    while (!pt.empty()) {
        // 0 U, 1 R, 2 D, 3 L
        auto x = pt.front();
        pt.pop();
        // cout << x.F.F sp x.F.S << '\n';
        if (!x.S) {
            rep(i, 0, 3) {
                int xx = x.F.F + dir_x[i], yy = x.F.S + dir_y[i];
                if (!vis[xx][yy] && xx >= 0 && xx <= n - 1 && yy >= 0 &&
                    yy <= m - 1) {
                    pt.push({{xx, yy}, 0});
                    vis[xx][yy] = 1;
                }
            }
        } else if (x.S && (x.F.F == 0 || x.F.S == 0 || x.F.F == n - 1 ||
                           x.F.S == m - 1)) {
            // cout << x.F.F sp x.F.S << '\n';
            ok = 1;
            de = {x.F.F, x.F.S};
            break;
        } else if (x.S) {
            // cout << x.F.F sp x.F.S << '\n';
            // cout << '\n';
            rep(i, 0, 3) {
                if (!vis[x.F.F + dir_x[i]][x.F.S + dir_y[i]] &&
                    !vis_h[x.F.F + dir_x[i]][x.F.S + dir_y[i]]) {
                    pt.push({{x.F.F + dir_x[i], x.F.S + dir_y[i]}, 1});
                    vis_h[x.F.F + dir_x[i]][x.F.S + dir_y[i]] = 1;
                    from[x.F.F + dir_x[i]][x.F.S + dir_y[i]] = i;
                }
            }
        }
    }
    if (!ok)
        cout << "NO\n";
    else {
        cout << "YES\n";
        vector<char> ans;
        while (de.F != a.F.F || de.S != a.F.S) {
            // cout << de.F sp de.S << '\n';
            int tmpF = de.F;
            ans.eb(dir[from[de.F][de.S]]);
            de.F -= dir_x[from[de.F][de.S]];
            de.S -= dir_y[from[tmpF][de.S]];
            // cout << de.F sp de.S << "\n\n";
        }
        cout << ans.size() << '\n';
        reverse(all(ans));
        for (char i : ans) cout << i;
    }
    return 0;
}

Shortest Routes I

Shortest Routes I
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int dis[100005];
vii g[100005];
int n, m, a, b, c;
bool vis[100005];

signed main() {
    ios;
    cin >> n >> m;
    rep(i, 1, m) cin >> a >> b >> c, g[a].eb(b, c);
    priority_queue<pii, vii, greater<pii>> pq;
    rep(i, 1, n) dis[i] = 1e18;
    dis[1] = 0, pq.push({0, 1});
    while (!pq.empty()) {
        pii cur = pq.top();
        pq.pop();
        if (vis[cur.S]) continue;
        vis[cur.S] = 1;
        for (pii i : g[cur.S]) {
            if (cur.F + i.S < dis[i.F]) {
                dis[i.F] = cur.F + i.S;
                pq.push({dis[i.F], i.F});
            }
        }
    }
    rep(i, 1, n) cout << dis[i] << ' ';
    return 0;
}

Shortest Routes II

Shortest Routes II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, m, q, a, b, c;
int dp[502][502];

signed main() {
    ios;
    rep(i, 0, 500) rep(j, 0, 500) dp[i][j] = 1e18 * (i!=j);
    cin >> n >> m >> q;
    rep(i, 1, m) {
        cin >> a >> b >> c;
        dp[a][b] = dp[b][a] = min(dp[a][b], c);
    }
    rep(k, 1, n) rep(i, 1, n) rep(j, 1, n) tomin(dp[i][j], dp[i][k] + dp[k][j]);
    while (q--) {
        cin >> a >> b;
        if (dp[a][b] == 1e18)
            cout << "-1\n";
        else
            cout << dp[a][b] << '\n';
    }
    return 0;
}

High Score

High Score
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, m, a, b, x;
vector<pair<pii, int>> g;
vi hg[3005], rg[3005];
int dis[3005];
bool bad = false;
bool vis[3005], rvis[3005];

void dfs(int rt){
    if(vis[rt]) return;
    vis[rt] = 1;
    for(int i : hg[rt]) dfs(i);
}

void rdfs(int rt){
    if(rvis[rt]) return;
    rvis[rt] = 1;
    for(int i : rg[rt]) rdfs(i);
}

signed main() {
    ios;
    cin >> n >> m;
    rep(i, 1, m) {
        cin >> a >> b >> x;
        g.pb({{a, b}, x});
        hg[a].eb(b), rg[b].eb(a);
    }
    dfs(1), rdfs(n);
    dis[1] = 0;
    rep(i, 2, n) dis[i] = -1e18;
    rep(j, 1, n) {
        for (auto i : g) {
            if (dis[i.F.S] < dis[i.F.F] + i.S) {
                dis[i.F.S] = dis[i.F.F] + i.S;
                if (j == n && vis[i.F.S] && rvis[i.F.S]) bad = 1;
            }
        }
    }
    if (bad)
        cout << "-1\n";
    else
        cout << dis[n] << '\n';
    return 0;
}

SPFA

High Score - SPFA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, m, a, b, x;
vii g[3005];
vi hg[3005], rg[3005];
int dis[3005], cnt[3005];
bool bad = false;
bool vis[3005], rvis[3005];
bool inq[3005];

void dfs(int rt) {
    if (vis[rt]) return;
    vis[rt] = 1;
    for (int i : hg[rt]) dfs(i);
}

void rdfs(int rt) {
    if (rvis[rt]) return;
    rvis[rt] = 1;
    for (int i : rg[rt]) rdfs(i);
}

signed main() {
    ios;
    cin >> n >> m;
    rep(i, 1, m) {
        cin >> a >> b >> x;
        g[a].eb(b, x);
        hg[a].eb(b), rg[b].eb(a);
    }
    dfs(1), rdfs(n);
    queue<int> q;
    rep(i, 1, n) dis[i] = -1e18;
    dis[1] = 0, q.push(1);
    bool bye = false;
    while (!q.empty() && !bye) {
        int cur = q.front();
        q.pop();
        inq[cur] = 0;
        for (auto i : g[cur]) {
            if (dis[i.F] < dis[cur] + i.S) {
                dis[i.F] = dis[cur] + i.S;
                if (!inq[i.F]) inq[i.F] = 1, q.push(i.F);
                cnt[i.F]++;
                if (cnt[i.F] >= n && vis[i.F] && rvis[i.F]) {
                    bad = 1;
                    bye = true;
                    break;
                }
                if (cnt[i.F] >= 2 * n) {
                    bye = 1;
                    break;
                }
            }
        }
    }
    if (bad)
        cout << "-1\n";
    else
        cout << dis[n] << '\n';
    return 0;
}

Flight Discount

Flight Discount
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, m, a, b, x;
vii g[100005], rg[100005];
int dis[100005], rdis[100005];
bool vis[100005], rvis[100005];

signed main() {
    ios;
    cin >> n >> m;
    rep(i, 1, m) cin >> a >> b >> x, g[a].eb(b, x), rg[b].eb(a, x);
    priority_queue<pii, vii, greater<pii>> pq;
    pq.push({0, 1}), dis[1] = 0;
    rep(i, 2, n) dis[i] = 1e18;
    while (!pq.empty()) {
        pii cur = pq.top();
        pq.pop();
        if (vis[cur.S]) continue;
        vis[cur.S] = 1;
        for (pii i : g[cur.S]) {
            if (cur.F + i.S < dis[i.F]) {
                dis[i.F] = cur.F + i.S;
                pq.push({dis[i.F], i.F});
            }
        }
    }
    pq.push({0, n}), rdis[n] = 0;
    rep(i, 1, n-1) rdis[i] = 1e18;
    while (!pq.empty()) {
        pii cur = pq.top();
        pq.pop();
        if (rvis[cur.S]) continue;
        rvis[cur.S] = 1;
        for (pii i : rg[cur.S]) {
            if (cur.F + i.S < rdis[i.F]) {
                rdis[i.F] = cur.F + i.S;
                pq.push({rdis[i.F], i.F});
            }
        }
    }
    int ans = 1e18;
    rep(i, 1, n) {
        for (pii j : g[i]) tomin(ans, dis[i] + j.S / 2 + rdis[j.F]);
    }
    cout << ans << '\n';
    return 0;
}

Cycle Finding

Cycle Finding
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

signed main() {
    ios;
    int n, m, nc = 0;
    cin >> n >> m;
    vii dis(n+1);
    vector<tuple<int, int, int> > g(m);
    for(auto &[a, b, c] : g) cin >> a >> b >> c;
    rep(i, 1, n){
        nc = 0;
        for(auto [a, b, c] : g){
            if(dis[b].F > dis[a].F+c){
                dis[b].F = dis[a].F + c;
                dis[b].S = a;
                nc = a;
            }
        }
    }

    if (nc) {
        cout << "YES\n";
        rep(i, 1, n) nc = dis[nc].S;
        cout << nc;
        vi ans;
        ans.eb(nc);
        for(int cur = dis[nc].S; cur != nc; cur = dis[cur].S) ans.eb(cur);
        reverse(all(ans));
        for(int i : ans) cout sp i;
    } else {
        cout << "NO\n";
    }
    return 0;
}

SPFA

Cycle Finding - SPFA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
 
vii g[3003];
pii dis[3003];
int n, m, a, b, c;
int nc = 0;
vi ans;
int vis[3003];
bool inq[3003];
 
signed main() {
    ios;
    cin >> n >> m;
    rep(i, 1, m) cin >> a >> b >> c, g[a].eb(b, c);
    
    queue<int> q;
    rep(i, 1, n) q.push(i), inq[i] = 1;
    while(!q.empty() && !nc){
        int cur = q.front();
        q.pop();
        inq[cur] = 0;
        for(pii i : g[cur]){
            if(dis[i.F].F > dis[cur].F + i.S){
                dis[i.F].F = dis[cur].F + i.S;
                dis[i.F].S = cur;
                vis[i.F]++;
                if(vis[i.F]>=n) {nc=i.F; break;}
                if(!inq[i.F]) q.push(i.F), inq[i.F] = 1;
            }
        }
    }
    
    if (nc) {
        cout << "YES\n";
        rep(i, 1, n) nc = dis[nc].S;
        cout << nc;
        vi ans;
        ans.eb(nc);
        for(int cur = dis[nc].S; cur != nc; cur = dis[cur].S) ans.eb(cur);
        reverse(all(ans));
        for(int i : ans) cout sp i;
    } else {
        cout << "NO\n";
    }
    return 0;
}

Flight Routes

Flight Routes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, m, k, a, b, w;
vi dis[100005];
vii g[100005];

signed main() {
    ios;
    cin >> n >> m >> k;
    rep(i, 1, m) cin >> a >> b >> w, g[a].eb(b, w);
    priority_queue<pii, vii, greater<pii> > pq;
    pq.push({0, 1});
    while (!pq.empty()) {
        pii cur = pq.top();
        pq.pop();
        if (dis[cur.S].size() >= k) continue;
        dis[cur.S].eb(cur.F);
        for (pii i : g[cur.S]) pq.push({cur.F + i.S, i.F});
    }
    for (int i : dis[n]) cout << i << ' ';
    return 0;
}

Round Trip II

Round Trip II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, m, a, b;
vi g[100005];
vi ans;
bool vis[100005];
bool cur_vis[100005];

int dfs(int rt) {
    if (cur_vis[rt] || !ans.empty()) return 0;
    vis[rt] = cur_vis[rt] = 1;
    for (int i : g[rt]) {
        if (cur_vis[i]) {
            ans.eb(i), ans.eb(rt);
            return i;
        } else if(!vis[i]) { // 若是vis[i]，則代表以i作為其中一點，一定不會形成環
            int flag = dfs(i);
            if (!flag && !ans.empty()) return 0;
            if (!flag) continue;
            ans.eb(rt);
            if (flag == rt) return 0;
            return flag;
        }
    }
    cur_vis[rt] = 0;
    return 0;
}

signed main() {
    ios;
    cin >> n >> m;
    rep(i, 1, m) cin >> a >> b, g[a].eb(b);
    rep(i, 1, n) if (!vis[i] && ans.empty()) dfs(i);
    if (ans.empty())
        cout << "IMPOSSIBLE";
    else {
        cout << ans.size() << '\n';
        reverse(all(ans));
        for (int i : ans) cout << i << ' ';
    }
    return 0;
}

Course Schedule

Course Schedule
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, m;
vi g[100005];
int deg[100005];

signed main() {
    ios;
    cin >> n >> m;
    rep(i, 1, m){
        int a, b;
        cin >> a >> b;
        deg[b]++;
        g[a].eb(b);
    }
    queue<int> q;
    vi ord;
    int cnt = 0;
    rep(i, 1, n) {
        if(deg[i]==0) q.push(i);
    }
    while(!q.empty()){
        ord.eb(q.front()), q.pop();
        cnt++;
        for(int i : g[ord.back()]){
            deg[i]--;
            if(deg[i]==0)q.push(i);
        }
    }
    if(cnt != n) {
        cout << "IMPOSSIBLE\n";
    } else {
        for(int i : ord) cout << i << ' ';
    }
    return 0;
}

Longest Flight Route

Longest Flight Route
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, m;
vi g[100005];
int deg[100005];
int dis[100005];
int last[100005];
bool vis[100005];

void dfs(int rt){
    if(vis[rt]) return;
    vis[rt] = 1;
    for(int i : g[rt]){
        deg[i]++;
        dfs(i);
    }
}

signed main() {
    ios;
    cin >> n >> m;
    rep(i, 1, m){
        int a, b;
        cin >> a >> b;
        g[a].eb(b);
    }
    dfs(1);
    if(!vis[n]){
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    vi st;
    st.eb(1);
    while(!st.empty()){
        int cur = st.back();
        st.pob();
        for(int i : g[cur]){
            deg[i]--;
            if(dis[i] < dis[cur]+1){
                dis[i] = dis[cur]+1;
                last[i] = cur;
            }
            if(deg[i]==0) st.eb(i);
        }
    }
    cout << dis[n]+1 << '\n';
    vi ans;
    for(int i = n; i!=0; i=last[i]){
        ans.eb(i);
    }
    reverse(all(ans));
    for(int i : ans) cout << i << ' ';
    return 0;
}

Game Routes

Game Routes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int mod = 1e9+7;

vi g[100005];
int deg[100005];
int n, m;
int way[100005];
bool vis[100005];

void dfs(int rt){
    if(vis[rt]) return;
    vis[rt] = 1;
    for(int i : g[rt]){
        deg[i]++;
        dfs(i);
    }
}

signed main() {
    ios;
    cin >> n >> m;
    rep(i, 1, m){
        int a, b;
        cin >> a >> b;
        g[a].eb(b);
    }
    dfs(1);
    way[1] = 1;
    vi v;
    v.eb(1);
    while(!v.empty()){
        int cur = v.back();
        v.pob();
        for(int i : g[cur]){
            way[i] += way[cur] %= mod;
            deg[i]--;
            if(deg[i] == 0) v.eb(i);
        }
    }
    cout << way[n] % mod << '\n';
    return 0;
}

Investigation

Investigation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int mod = 1e9+7;

int n, m;
vii g[100005];
int dis[100005];
int way[100005];
int max_route[100005];
int min_route[100005];
bool vis[100005];

signed main() {
    ios;
    cin >> n >> m;
    rep(i, 1, m){
        int a, b, c;
        cin >> a >> b >> c;
        g[a].eb(b,c);
    }
    fill(dis, dis+n+1, 1e18);
    fill(min_route, min_route+n+1, 1e18);
    priority_queue<pii, vii, greater<pii>> pq;
    pq.push({0, 1}), dis[1]=0, way[1]=1, max_route[1]=min_route[1]=0;
    while(!pq.empty()){
        pii cur = pq.top();
        pq.pop();
        if(vis[cur.S]) continue;
        vis[cur.S]=1;
        for(pii i: g[cur.S]){
            if(dis[i.F] == cur.F+i.S){
                (way[i.F] += way[cur.S]) %= mod;
                tomax(max_route[i.F], max_route[cur.S]+1);
                tomin(min_route[i.F], min_route[cur.S]+1);
            }
            if(dis[i.F] > cur.F+i.S){
                dis[i.F] = cur.F+i.S;
                way[i.F] = way[cur.S];
                max_route[i.F] = max_route[cur.S]+1;
                min_route[i.F] = min_route[cur.S]+1;
                pq.push({dis[i.F], i.F});
            }
        }
    }
    cout << dis[n] sp way[n] sp min_route[n] sp max_route[n] << '\n';
    return 0;
}

Planets Queries I

Planets Queries I
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, q;
int ch[200005][31]; //[i][j] -> 2^j th child of i

void build(){
    rep(i, 1, 30)
        rep(j, 1, n)
            ch[j][i] = ch[ch[j][i-1]][i-1];
}

int query(int x, int k){
    for(int i = 0;k!=0; k>>=1, i++)
        if(k & 1)
            x = ch[x][i];
    return x;
}

signed main() {
    ios;
    cin >> n >> q;
    rep(i, 1, n) cin >> ch[i][0];
    build();
    while(q--){
        int x, k;
        cin >> x >> k;
        cout << query(x, k) << '\n';
    }
    return 0;
}

Planets Queries II

Planets Queries II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, q;
int go[200005];
vi rgo[200005];
int boss[200005];
int sizeC[200005];
int idxC[200005];  // from is big
int idxA[200005];  // from is big
bool inC[200005];
bool tmpC[200005];
bool vis[200005];

int find_boss(int ch) {
    if (ch == boss[ch]) return ch;
    return boss[ch] = find_boss(boss[ch]);
}

int dfs(int rt) {
    if (vis[rt]) return rt;
    vis[rt] = 1;
    int flag = dfs(go[rt]);
    if (!sizeC[find_boss(rt)]) {
        inC[rt] = 1;
        idxC[rt] = idxC[go[rt]] + 1;
        if (flag == rt) sizeC[find_boss(rt)] = idxC[rt];
    }
    return flag;
}

void dfs2(int rt, int id) {
    idxA[rt] = id;
    for (int i : rgo[rt])
        if (!inC[i]) dfs2(i, id + 1);
}

int ch[200005][31];  //[i][j] -> 2^j th child of i

void build() { rep(i, 1, 30) rep(j, 1, n) ch[j][i] = ch[ch[j][i - 1]][i - 1]; }

int query(int x, int k) {
    for (int i = 0; k != 0; k >>= 1, i++)
        if (k & 1) x = ch[x][i];
    return x;
}

signed main() {
    ios;
    cin >> n >> q;
    rep(i, 1, n) boss[i] = i;
    rep(i, 1, n) cin >> go[i], rgo[go[i]].eb(i), boss[find_boss(i)] = boss[find_boss(go[i])], ch[i][0] = go[i];
    rep(i, 1, n) dfs(i);
    rep(i, 1, n) if (inC[i]) dfs2(i, 0);
    build();
    while (q--) {
        int a, b;
        cin >> a >> b;
        if (find_boss(a) != find_boss(b))
            cout << "-1\n";
        else {
            if (inC[a] && inC[b])
                cout << (idxC[a] - idxC[b] + sizeC[find_boss(a)]) % sizeC[find_boss(a)] << '\n';
            else if (!inC[a] && inC[b])
                cout << idxA[a] + (idxC[query(a, idxA[a])] - idxC[b] + sizeC[find_boss(a)]) % sizeC[find_boss(a)] << '\n';
            else if (idxA[a] >= idxA[b] && query(a, idxA[a] - idxA[b]) == b)
                cout << idxA[a] - idxA[b] << '\n';
            else
                cout << "-1\n";
        }
    }
    return 0;
}

Planets Cycles

Planets Cycles
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n;
int boss[200005];
int go[200005];
vi rgo[200005];
int idxA[200005];
int sizeC[200005];
bool inC[200005];
bool vis[200005];

int find_boss(int ch) {
    if (ch == boss[ch]) return ch;
    return boss[ch] = find_boss(boss[ch]);
}

int dfs(int rt, int &cSize) {
    if (vis[rt]) return rt;
    vis[rt] = 1;
    int flag = dfs(go[rt], cSize);
    if (!sizeC[find_boss(rt)]) {
        inC[rt] = 1;
        cSize++;
        if (rt == flag) sizeC[find_boss(rt)] = cSize;
    }
    return flag;
}

void dfs2(int rt, int id) {
    idxA[rt] = id;
    for (int i : rgo[rt])
        if (!inC[i]) dfs2(i, id + 1);
}

signed main() {
    ios;
    cin >> n;
    rep(i, 1, n) boss[i] = i;
    rep(i, 1, n) cin >> go[i], rgo[go[i]].eb(i), boss[find_boss(i)] = boss[find_boss(go[i])];
    for (int i = 1, cSize = 0; i <= n; i++, cSize = 0) dfs(i, cSize);
    rep(i, 1, n) if (inC[i]) dfs2(i, 0);
    rep(i, 1, n) { cout << idxA[i] + sizeC[find_boss(i)] << ' '; }
    return 0;
}

Road Reparation

Road Reparation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, m, edge = 0, cost = 0;
int boss[200005];
vector<tuple<int, int, int>> g, tg;

int find_boss(int ch){
    if(ch == boss[ch]) return ch;
    return boss[ch] = find_boss(boss[ch]);
}

signed main() {
    ios;
    cin >> n >> m;
    g.resize(m);
    rep(i, 1, n) boss[i] = i;
    for(auto &[w, u, v] : g) cin >> u >> v >> w;
    sort(all(g));
    for(auto [w, u, v] : g){
        if(find_boss(u) == find_boss(v)) continue;
        boss[find_boss(u)] = boss[find_boss(v)];
        cost += w;
        edge++;
    }
    if(edge != n-1) cout << "IMPOSSIBLE\n";
    else cout << cost << '\n';
    return 0;
}

Road Construction

Road Construction
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, m, maxB;
int boss[100005];
int sizeB[100005];

int find_boss(int ch) {
    if (ch == boss[ch]) return ch;
    return boss[ch] = find_boss(boss[ch]);
}

signed main() {
    ios;
    cin >> n >> m;
    rep(i, 1, n) boss[i] = i, sizeB[i] = 1;
    while (m--) {
        int a, b;
        cin >> a >> b;
        if (find_boss(a) != find_boss(b))
            n--, tomax(maxB, sizeB[find_boss(b)] += sizeB[find_boss(a)]), boss[find_boss(a)] = boss[find_boss(b)];
        cout << n sp maxB << '\n';
    }
    return 0;
}

Flight Routes Check

Flight Routes Check
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, m;
int no = -1;
vi g[100005], rg[100005];
bool vis[100005], rvis[100005];

void dfs(int rt){
    if(vis[rt]) return;
    vis[rt] = 1;
    for(int i : g[rt]) dfs(i);
}

void rdfs(int rt){
    if(rvis[rt]) return;
    rvis[rt] = 1;
    for(int i : rg[rt]) rdfs(i);
}

signed main() {
    ios;
    cin >> n >> m;
    rep(i, 1, m){
        int a, b;
        cin >> a >> b;
        g[a].eb(b);
        rg[b].eb(a);
    }
    dfs(1), rdfs(1);
    rep(i, 1, n){
        if(!vis[i]) {
            cout << "NO\n" << 1 sp i << '\n';
            return 0;
        }
        if(!rvis[i]){
            cout << "NO\n" << i sp 1 << '\n';
            return 0;
        }
    }
    cout << "YES\n";
    return 0;
}

Planets and Kingdoms

Planets and Kingdoms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int id = 0;
int n, m;
vi g[100005], rg[100005], ord;
int idx[100005];
bool vis[100005], rvis[100005];

void dfs(int rt){
    if(vis[rt]) return;
    vis[rt] = 1;
    for(int i : g[rt]) dfs(i);
    ord.eb(rt);
}

void rdfs(int rt){
    if(rvis[rt]) return;
    rvis[rt] = 1;
    for(int i : rg[rt]) rdfs(i);
    idx[rt] = id;
}

signed main() {
    ios;
    cin >> n >> m;
    rep(i, 1, m) {
        int a, b;
        cin >> a >> b;
        g[a].eb(b);
        rg[b].eb(a);
    }
    rep(i, 1, n) dfs(i);
    reverse(all(ord));
    for(int i : ord) if(!rvis[i]) id++,rdfs(i);
    cout << id << '\n';
    rep(i, 1, n) cout << idx[i] << ' ';
    return 0;
}

Giant Pizza

Giant Pizza
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

#define n(a) ((a + m) % (2 * m) == 0 ? 2 * m : (a + m) % (2 * m))

int n, m, id = 0;
vi g[200005], rg[200005], ord;
int idx[200005];
bool vis[200005], rvis[200005];

void dfs(int rt) {
    if (vis[rt]) return;
    vis[rt] = 1;
    for (int i : g[rt]) dfs(i);
    ord.eb(rt);
}

void rdfs(int rt) {
    if (rvis[rt]) return;
    rvis[rt] = 1;
    idx[rt] = id;
    for (int i : rg[rt]) rdfs(i);
}

signed main() {
    ios;
    cin >> n >> m;
    rep(i, 1, n) {
        int a, b;
        char aa, bb;
        cin >> aa >> a >> bb >> b;
        if (aa == '-') a = n(a);
        if (bb == '-') b = n(b);
        g[n(a)].eb(b);
        g[n(b)].eb(a);
        rg[b].eb(n(a));
        rg[a].eb(n(b));
    }
    rep(i, 1, m * 2) dfs(i);
    reverse(all(ord));
    for (int i : ord)
        if (!rvis[i]) id++, rdfs(i);
    rep(i, 1, m * 2) 
        if (idx[i] == idx[n(i)]) {
            cout << "IMPOSSIBLE\n";
            return 0;
        }
    rep(i, 1, m) 
        if(idx[i]>idx[n(i)]) cout << "+ ";
        else cout << "- ";
    return 0;
}

Coin Collector

Coin Collector
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, m, id = 0, ans = 0;
vi g[100005], rg[100005], scc_g[100005], ord;
int idx[100005], scc_room[100005], room[100005], dp[100005];
bool vis[100005], rvis[100005], scc_vis[100005];

void dfs(int rt){
    if(vis[rt]) return;
    vis[rt] = 1;
    for(int i : g[rt]) dfs(i);
    ord.eb(rt);
}

void rdfs(int rt){
    if(rvis[rt]) return;
    rvis[rt] = 1;
    for(int i : rg[rt]) rdfs(i);
    idx[rt] = id;
    scc_room[id] += room[rt];
}

int scc_dfs(int rt){
    if(scc_vis[rt]) return dp[rt];
    scc_vis[rt] = 1;
    int max_room = 0;
    for(int i : scc_g[rt]) tomax(max_room, scc_dfs(i));
    return dp[rt] = scc_room[rt] + max_room;
}

signed main() {
    ios;
    cin >> n >> m;
    rep(i, 1, n) cin >> room[i];
    rep(i, 1, m){
        int a, b;
        cin >> a >> b;
        g[a].eb(b), rg[b].eb(a);
    }
    rep(i, 1, n) dfs(i);
    reverse(all(ord));
    for(int i : ord) if(!rvis[i]) id++, rdfs(i);
    rep(i, 1, n) for(int j : g[i]) if(idx[i]!=idx[j])
        scc_g[idx[i]].eb(idx[j]);
    // rep(i, 1, n) err(i sp idx[i] sp room[i] sp scc_room[idx[i]]);
    // rep(i, 1, id) for(int j : scc_g[i]) err(i sp j);
    rep(i, 1, id) tomax(ans, scc_dfs(i));
    cout << ans << '\n';
    return 0;
}

Mail Delivery

Mail Delivery
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, m, odd=1, ed=1, cnt_odd = 0;
int deg[100005];
vi g[100005], ans;
bool vis[100005];
map<pii, bool> evis;

void dfs(int rt){
    vis[rt] = 1;
    while(!g[rt].empty()){
        int cur = g[rt].back();
        g[rt].pob();
        if(evis[{rt, cur}]) continue;
        evis[{rt, cur}] = 1, evis[{cur, rt}] = 1, dfs(cur);
        ans.eb(rt);
    }
}

signed main() {
    ios;
    cin >> n >> m;
    si cg;
    rep(i, 1, m){
        int a, b;
        cin >> a >> b;
        g[a].eb(b), g[b].eb(a);
        deg[a]++, deg[b]++;
        cg.insert(a), cg.insert(b);
    }
    rep(i, 1, n) if(deg[i]&1) ed = odd, odd = i, cnt_odd++;
    if(cnt_odd!=0) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    dfs(odd);
    for(int i : cg) if(!vis[i]) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    reverse(all(ans));
    for(int i : ans) cout << i << ' ';
    cout << ed << '\n';
    return 0;
}

set

Mail Delivery - set
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, m, st=1, ed=1, cnt_odd = 0;
si g[100005];
vi ans;

void dfs(int rt){
    while(!g[rt].empty()){
        int cur = *g[rt].begin();
        g[rt].erase(g[rt].begin());
        g[cur].erase(rt);
        dfs(cur);
    }
    ans.eb(rt);
}

signed main() {
    ios;
    cin >> n >> m;
    si cg;
    rep(i, 1, m){
        int a, b;
        cin >> a >> b;
        g[a].insert(b), g[b].insert(a);
    }
    rep(i, 1, n) if(g[i].size()&1) ed = st, st = i, cnt_odd++;
    if(cnt_odd!=0) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    dfs(st);
    rep(i, 1, n) if(!g[i].empty()) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    reverse(all(ans));
    for(int i : ans) cout << i << ' ';
    return 0;
}

De Bruijn Sequence

De Bruijn Sequence
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n;
vi g[100005], ans;

void dfs(int rt){
    while(!g[rt].empty()){
        int cur = g[rt].back();
        g[rt].pob();
        dfs(cur);
        ans.eb(rt&1);
    }
}

signed main() {
    ios;
    cin >> n;
    rev(i, (1<<(n-1))-1, 0){
        int nxt = (i<<1) & ((1<<(n-1))-1);
        g[i].eb(nxt);
        g[i].eb(nxt+1);
    }
    dfs(0);
    reverse(all(ans));
    rep(i,1,n-1) cout << 0;
    if(n==1) cout << "01";
    else for(int i : ans) cout << i;
    return 0;
}

Teleporters Path

Teleporters Path
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, m, deg[100005];
vi g[100005], ans;

void dfs(int rt){
    while(!g[rt].empty()){
        int cur = g[rt].back();
        g[rt].pob();
        dfs(cur);
    }
    ans.eb(rt);
}

signed main() {
    ios;
    cin >> n >> m;
    rep(i, 1, m){
        int a, b;
        cin >> a >> b;
        g[a].eb(b);
        deg[a]++, deg[b]++;
    }
    rep(i, 1+1, n-1) if(deg[i]&1){
        cout << "IMPOSSIBLE\n";
        return 0;
    } 
    if(!((deg[1]&1) && (deg[n]&1))){
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    dfs(1);
    rep(i, 1, n) if(!g[i].empty()){
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    reverse(all(ans));
    for(int i : ans) cout << i << ' ';
    return 0;
}

Hamiltonian Flights

Hamiltonian Flights
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int mod = 1e9 + 7;
int n, m;
int dp[21][2000006];
int g[21][21];

signed main() {
    ios;
    cin >> n >> m;
    rep(i, 1, m) {
        int a, b;
        cin >> a >> b;
        g[a][b]++;
    }
    dp[1][1] = 1;
    // int op = 0;
    rep(i, 1, (1 << n) - 1) {
        rep(j, 1, n) {
            int pos = (1 << (j - 1));
            if (!(i & pos)) continue;
            rep(k, 1, n) {
                if (!g[k][j]) continue;
                (dp[j][i] += dp[k][i^pos] * g[k][j]);
                // op++;
            }
            dp[j][i] %= mod;
        }
        i++;  // first digit must be 1 because path start at one.
    }
    cout << dp[n][(1 << n) - 1] % mod << '\n';
    return 0;
}

Knight’s Tour

Knight's Tour
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int x, y;
int dir[8][2] = {{1, 2}, {2, 1}, {1, -2}, {-2, 1}, {-1, 2}, {2, -1}, {-1, -2}, {-2, -1}};
bool vis[10][10];
vii ans;
int out[10][10];

bool dfs(int x, int y, int cnt) {
    if (vis[x][y]) return 0;
    if (cnt == 63) {
        ans.eb(x, y);
        return 1;
    }
    vis[x][y] = 1;
    cnt++;
    vector<pair<int, pii>> go;
    rep(i, 0, 7) {
        if (x + dir[i][0] > 8 || x + dir[i][0] < 1 || y + dir[i][1] > 8 || y + dir[i][1] < 1) continue;
        int nx = x + dir[i][0], ny = y + dir[i][1], deg = 0;
        rep(i, 0, 7) if (!(nx + dir[i][0] > 8 || nx + dir[i][0] < 1 || ny + dir[i][1] > 8 || ny + dir[i][1] < 1)) deg++;
        go.pb({deg, {nx, ny}});
    }
    sort(all(go));
    for (auto i : go)
        if (dfs(i.S.F, i.S.S, cnt)) {
            ans.eb(x,y);
            return 1;
        }
    vis[x][y] = 0;
    return 0;
}

signed main() {
    ios;
    cin >> x >> y;
    dfs(x, y, 0);
    reverse(all(ans));
    rep(i, 1, 64) { out[ans[i - 1].F][ans[i - 1].S] = i;}
    rep(i, 1, 8) {
        rep(j, 1, 8) cout << out[j][i] << ' ';
        cout << '\n';
    }
    return 0;
}

Download Speed

Download Speed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, m;
int adj[502][502];
bool vis[502];

bool dfs(int rt, vector<int> &path, int threshold) {
    if (vis[rt]) return false;
    vis[rt] = 1;
    if (rt == n) {
        path.push_back(rt);
        return true;
    }
    rep(i, 1, n) {
        if (adj[rt][i] < threshold) continue;
        if (dfs(i, path, threshold)) {
            path.push_back(rt);
            return true;
        }
    }
    return false;
}

signed main() {
    ios;
    cin >> n >> m;
    int threshold = 0;
    rep(i, 1, m) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a][b] += c;
        tomax(threshold, c);
    }
    int ans = 0;
    while (threshold > 0) {
        vector<int> path;
        memset(vis, 0, sizeof(vis));
        if (dfs(1, path, threshold)) {
            reverse(path.begin(), path.end());
            int k = path.size();
            int flow = 1e9;
            rep (i, 0, k-2) tomin(flow, adj[path[i]][path[i + 1]]);
            ans += flow;
            rep (i, 0, k-2) {
                adj[path[i]][path[i + 1]] -= flow;
                adj[path[i + 1]][path[i]] += flow;
            }
        } else threshold >>= 1;
    }
    cout << ans << "\n";
    return 0;
}

Police Chase

Police Chase
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, m, ans;
int g[502][502];
bool vis[502];

bool dfs(int rt){
    if(vis[rt]) return 0;
    if(rt == n) return 1;
    vis[rt] = 1;
    rep(i, 1, n){
        if(g[rt][i] && dfs(i)){
            g[rt][i]--, g[i][rt]++;
            return 1;
        }
    }
    return 0;
}

signed main() {
    ios;
    cin >> n >> m;
    rep(i, 1, m){
        int a, b;
        cin >> a >> b;
        g[a][b] = g[b][a] = 1;
    }
    while(dfs(1)) memset(vis, 0, sizeof(vis)), ans++;
    cout << ans << '\n';
    rep(i, 1, n){
        rep(j, 1, n){
            if((vis[i] ^ vis[j]) && !g[i][j] && g[j][i]) cout << i sp j << '\n';
        }
    }
    return 0;
}

School Dance

School Dance
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, m, k, ans;
int g[1003][1003];
bool vis[1003];
vi go[1003];

bool dfs(int rt){
    if(vis[rt]) return 0;
    if(rt == 1001) return 1;
    vis[rt] = 1;
    rep(i, 1, 1001){
        if(g[rt][i] && dfs(i)){
            g[rt][i]--, g[i][rt]++;
            return 1;
        }
    }
    return 0;
}

signed main() {
    ios;
    cin >> n >> m >> k;
    rep(i, 1, k){
        int a, b;
        cin >> a >> b;
        g[0][a] = g[a][b+500] = g[b+500][1001] = 1;
        go[0].eb(a), go[a].eb(b+500), go[b+500].eb(1001);
    }
    while(dfs(0)) memset(vis, 0, sizeof(vis)), ans++;
    cout << ans << '\n';
    while(ans--){
        int a, b, s = 0;
        while(s != 1001){
            a=b, b=s;
            for(int i : go[s]) 
                if(!g[s][i] && g[i][s]){
                    g[s][i]=1;
                    s=i;
                    break;
                }
        }
        cout << a sp b-500 << '\n';
    }
    return 0;
}

Distinct Routes

Distinct Routes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
/* TYPES  */
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define vc vector
#define vi vector<int>
#define vii vector<pii>
#define mii map<int, int>
#define si set<int>
/* UTILS */
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rev(i, a, b) for (int i = a; i >= b; --i)
#define tomax(a, b) (a) = max((a), (b))
#define tomin(a, b) (a) = min((a), (b))
#define all(a) a.begin(), a.end()
#define rall(a) (a).rbegin(), (a).rend()
#define pob pop_back
#define pb push_back
#define eb emplace_back
#define ins insert
#define err(a) cerr << #a << ": " << a << "\n"
#define sp << " " <<
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, m, ans = 0;
int g[502][502];
bool vis[502];
vi go[502];

bool dfs(int rt){
    if(vis[rt]) return 0;
    if(rt == n) return 1;
    vis[rt] = 1;
    rep(i, 1, n){
        if(g[rt][i] && dfs(i)) {
            g[rt][i]--, g[i][rt]++;
            return 1;
        }
    }
    return 0;
}

signed main() {
    ios;
    cin >> n >> m;
    rep(i, 1, m){
        int a, b;
        cin >> a >> b;
        g[a][b]++;
        go[a].eb(b);
    }
    while(dfs(1)) memset(vis, 0, sizeof(vis)), ans++;
    cout << ans << '\n';
    while(ans--){
        vi path(1,1);
        int s = 1;
        while(s!=n){
            for(int i : go[s])
                if(!g[s][i] && g[i][s]){
                    g[i][s]=0;
                    s=i;
                    path.eb(i);
                    break;
                }
        }
        cout << path.size() << '\n';
        for(int i : path) cout << i << ' ';
        cout << '\n';
    }
    return 0;
}