Submission #1135829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135829		DangKhoizzzz	Džumbus (COCI19_dzumbus)	C++20	0 / 110	54 ms	1092 KiB

dzumbus

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define ar3 array <int , 3>

using namespace std;

const int INF = 1e9 + 7;
const int maxn = 1e3 + 5;
const int maxk = 1e3 + 5;

vector <int> g[maxn];
int n , m , d[maxn] , need[maxn];
bool vis[maxn];

void bfs(int start)
{
    for(int i = 1; i <= n; i++) vis[i] = 0;

    int cursum = 0 , cnt = 0;

    priority_queue <pii , vector <pii> , greater <pii>> Q;
    Q.push({d[start] , start});

    while(!Q.empty())
    {
        int u = Q.top().se;
        Q.pop();

        if(vis[u]) continue;
        vis[u] = 1;

        cnt++;
        cursum += d[u];

        need[cnt] = min(need[cnt] , cursum);

        for(int v: g[u])
        {
            Q.push({d[v] , v});
        }
    }
}

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> d[i];

    for(int i = 1; i <= m; i++)
    {
        int u , v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for(int i = 1; i <= n; i++) need[i] = INF*INF;
    for(int i = 1; i <= n; i++) bfs(i);

    for(int i = n-1; i >= 1; i--)
    {
        need[i] = min(need[i] , need[i+1]);
    }

    int q; cin >> q;

    while(q--)
    {
        int s; cin >> s;
        int res = upper_bound(need + 0, need + n + 1 , s) - need - 1;

        if(res < 2) cout << 0 << '\n';
        else cout << res << '\n';
    }
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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