제출 #1226945

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226945		dksnfjkfnwkfw	Džumbus (COCI19_dzumbus)	C++20	0 / 110	17 ms	836 KiB

dzumbus

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

#define IO(x) freopen(x".inp", "r", stdin); freopen(x".out", "w", stdout)
#define sonic ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using ll = long long;

int main() {
   
    sonic;

    int n, m;
    cin >> n >> m;

    vector<int> d(n);
    for (int& x : d) cin >> x;

    vector<vector<int>> adj(n);
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        --u; --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // Tìm đường thẳng bằng BFS
    vector<int> path;
    vector<bool> vis(n, false);

    // tìm đầu mút của đường thẳng
    int start = 0;
    for (int i = 0; i < n; ++i)
        if (adj[i].size() == 1) {
            start = i;
            break;
        }

    // đi theo đường thẳng
    int curr = start, prev = -1;
    while (curr != -1) {
        path.push_back(curr);
        vis[curr] = true;
        int next = -1;
        for (int nei : adj[curr]) {
            if (!vis[nei]) {
                next = nei;
                break;
            }
        }
        prev = curr;
        curr = next;
    }

    // dsum[i] là tổng D của đoạn từ path[0] đến path[i]
    int len = path.size();
    vector<ll> dsum(len + 1, 0);
    for (int i = 0; i < len; ++i)
        dsum[i + 1] = dsum[i] + d[path[i]];

    int q;
    cin >> q;
    while (q--) {
        int S;
        cin >> S;
        int res = 0;

        // Two pointers
        int l = 0;
        for (int r = 1; r <= len; ++r) {
            while (dsum[r] - dsum[l] > S) ++l;
            // đoạn [l, r-1] hợp lệ
            if (r - l >= 2) res = max(res, r - l);
        }

        cout << res << '\n';
    }

    return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30