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

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 1e5 + 7, mod = 1e9 + 7;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> vis(n + 1);

    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        if (x > y) swap(x, y);
        if (x + 1 == y) vis[x] = 1;
    }
    for (int i = 1; i < n; i++) {
        if (!vis[i]) {
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

 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

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 2e5 + 7, mod = 1e9 + 7;

struct Node {
    int cnt, penalty;
    int unknown, unknownPenalty;
};

struct Log {
    string teamName;
    char problemID;
    int time;
    string status;
} logs[N];

bool cmp(const Log &a, const Log &b) {
    if (a.time != b.time) return a.time < b.time;
    if (a.teamName != b.teamName) return a.teamName < b.teamName;
    return a.problemID < b.problemID;
}

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> logs[i].teamName >> logs[i].problemID >> logs[i].time >> logs[i].status;
    }
    sort(logs + 1, logs + n + 1, cmp);
    map<string, Node> mp;
    vector<string> ans;
    map<pair<string, char>, int> submission;
    for (int i = 1; i <= n; i++) {
        string teamName = logs[i].teamName;
        char problemID = logs[i].problemID;
        int time = logs[i].time;
        string status = logs[i].status;
        if (submission[{teamName, problemID}] == 1) continue;
        if (status == "Accepted") {
            mp[teamName].cnt++;
            mp[teamName].penalty += time + -20 * submission[{teamName, problemID}];
            submission[{teamName, problemID}] = 1;
        } else if (status == "Rejected") {
            submission[{teamName, problemID}]--;
        } else {
            mp[teamName].unknown++;
            mp[teamName].unknownPenalty += time + -20 * submission[{teamName, problemID}];
            submission[{teamName, problemID}] = 1;
        }
    }
    pair<int, int> mx = {0, 9999999};
    for (auto &[teamName, node] : mp) {
        if (node.cnt > mx.first) {
            mx = {node.cnt, node.penalty};
        } else if (node.cnt == mx.first && node.penalty <= mx.second) {
            mx = {node.cnt, node.penalty};
        }
    }
    for (auto &[teamName, node] : mp) {
        pair<int, int> now = {node.cnt + node.unknown, node.penalty + node.unknownPenalty};
        if (now.first > mx.first || (now.first == mx.first && now.second <= mx.second)) {
            ans.push_back(teamName);
        }
    }
    sort(ans.begin(), ans.end());
    for (auto &it : ans) {
        cout << it << " ";
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 1e5 + 7, mod = 1e9 + 7;

void solve() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= k; i++) cout << i << " ";
    cout << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

 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;
using P = tuple<int,int,int>;
#define endl "\n"
typedef long long ll;

const int INF = 1e9;

void solve() {
    int n, m, V, T;             
    cin >> n >> m >> V >> T;

    vector<pair<int,int>> g[n + 1];
    for (int i = 0; i < m; ++i) {
        int a, b, c;            
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    vector<int> bag(n + 1, INF), rem(n + 1, -1);

    
    priority_queue<P, vector<P>, greater<P>> pq;

    bag[T] = 1;
    rem[T] = V;
    pq.push({1, -V, T});

    while (!pq.empty()) {
        auto [b, neg, u] = pq.top(); pq.pop();
        int r = -neg;
        if (b > bag[u] || (b == bag[u] && r < rem[u])) continue;

        for (auto [v, w] : g[u]) {
            int nb = b, nr = r - w;
            if (nr < 0) {              
                nb++;
                nr = V - w;
            }
            if (nb < bag[v] || (nb == bag[v] && nr > rem[v])) {
                bag[v] = nb;
                rem[v] = nr;
                pq.push({nb, -nr, v});
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        cout << (bag[i] == INF ? -1 : bag[i]) << (i == n ? '\n' : ' ');
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;  
    // cin >> t;
    while (t--) solve();
    return 0;
}

  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;
#define endl "\n"
typedef long long ll;

const int N = 1e5 + 7, mod = 1e9 + 7;
const ll INF = 1e18;

void solve() { 
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int,int>>> G(n + 1);
    vector<vector<int>> tp(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        tp[u].push_back(v);
        tp[v].push_back(u);
    }
    vector<ll> f0(n + 1, INF), f1(n + 1, INF);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    f0[1] = 0;
    pq.push({0, 1});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > f0[u]) continue;
        for (auto [v, w] : G[u]) {
            if (f0[v] > d + w) {
                f0[v] = d + w;
                pq.push({f0[v], v}); 
            }
        }
    }
    ll ans = 0;
    ans = accumulate(f0.begin() + 1, f0.end(), 0LL);
    cout << ans << "\n";
    vector<ll> val(n + 1, 0), g(n + 1);
    auto dfs1 = [&](auto self, int u, int p) -> ll {
        ll res = val[u];
        for (auto [v, w] : G[u]) {
            if (v == p) continue;
            res = min(res, self(self, v, u) + w);
        }
        g[u] = res;
        return res;
    };

    auto dfs2 = [&](auto self, int u, int p, ll dis) -> void {
        if (dis != INF) {
            g[u] = min(g[u], dis);
        }
        for (auto [v, w] : G[u]) {
            if (v == p) continue;
            ll res = min(dis, (g[u] == g[v] + w) ? INF : g[u]);
            if (res != INF) {
                res += w;
            }
            self(self, v, u, res);
        }
    };

    for (int i = 1; i <= n; i++) {
        val.assign(n + 1, INF);
        for (int u = 1; u <= n; u++) {
            for (auto v : tp[u]) {
                val[u] = min(val[u], f0[v]);
            }
        }
        g.assign(n + 1, INF);
        dfs1(dfs1, 1, 0);
        dfs2(dfs2, 1, 0, INF);
        for (int j = 1; j <= n; j++) {
            f1[j] = min(f0[j], g[j]);
        }
        ans = accumulate(f1.begin() + 1, f1.end(), 0LL);
        cout << ans << "\n";
        if (ans == accumulate(f0.begin() + 1, f0.end(), 0LL)) {
            for (int k = i + 1; k <= n; k++) {
                cout << ans << "\n";
            }
            break;
        }
        f0 = f1;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

 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;
#define endl "\n"
typedef long long ll;

const int N = 1e5 + 7, mod = 1e9 + 7;

void solve() {
    int n, m;
    cin >> m >> n;
    vector<pair<int, int>> p(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> p[i].first >> p[i].second;
    }
    sort(p.begin() + 1, p.end());
    int ans = n;
    priority_queue<int, vector<int>, greater<>> pq;
    for (int i = 1; i <= m; i++) {
        if (i < m && p[i].first == p[i + 1].first) {
            pq.push(p[i].second);
            continue;
        } 
        pq.push(p[i].second);
        int r = i < m ? p[i + 1].first : n;
        for (int j = p[i].first + 1; j <= r; j++) {
            while (pq.size() && pq.top() < j) {
                pq.pop();
            }
            if (pq.size()) {
                ans--;
                pq.pop();
            } else {
                break;
            }
        }
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}