제출 #1123903

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

dzumbus

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

typedef vector<int> vi;
typedef vector<char> vc;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;

#define sep ' '
#define F first
#define S second
#define fastIO   ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define kill(x) {cout << x << endl;return;}
#define sz(x) int(x.size())
#define SP(x) setprecision(x) 
#define mod(x) (1ll*x%M+M)%M
#define pq priority_queue
#define mid (l+r)/2
// #define mid2 (l+r+1)/2
#define pll pair<ll, ll>
#define REP(i, k) for (int i = 0 ; i < k ; i ++)
#define MP make_pair
#define us unordered_set
#define int ll

const int INF = 1e9+10;
const int N = 1e3+10;
int n, m, q;
int d[N];
vi adj[N];
ll dy[N][N]; // drunk yes
ll dn[N][N]; // drunk no
ll nd[N][N]; // not drunk
ll ans[N], ans_dy[N], ans_dn[N], ans_nd[N];
bool vis[N];
int sz[N];
ll tmp;

void dfs(int v) {
    vis[v] = true;
    sz[v]++;
    dy[v][0] = INF;
    dn[v][0] = d[v];
    nd[v][0] = 0;

    for(int u: adj[v]) {
        if (vis[u]) continue;
        dfs(u);
        sz[v] += sz[u];

        for(int i = sz[v] ; i >= 0 ; i --) {
            dy[v][i] = dy[v][0] + min({dy[u][i], nd[u][i], (i-1 < 0 ? INF : dn[u][i-1])});
            dn[v][i] = dn[v][0] + nd[u][i];
            nd[v][i] = nd[v][0] + min({nd[u][i], dn[u][i], dy[u][i]});
            for(int j = 1 ; j <= min(i, sz[u]) ; j ++) {
                dy[v][i] = min(dy[v][i], dy[v][j] + min({dy[u][i-j], nd[u][i-j], (i-j-1 < 0 ? INF : dn[u][i-j-1])}));
                dn[v][i] = min(dn[v][i], dn[v][j] + nd[u][i-j]);
                nd[v][i] = min(nd[v][i], nd[v][j] + min({nd[u][i-j], dn[u][i-j], dy[u][i-j]}));
            }
        }
    }
}




void solve() {
	cin >> n >> m;

    REP(i, N) {
        fill(dy[i], dy[i]+N, INF);
        fill(dn[i], nd[i]+N, INF);
        fill(nd[i], nd[i]+N, INF);
    }
    fill(ans, ans+N, INF);
    fill(ans_dn, ans_dn+N, INF);
    fill(ans_dy, ans_dy+N, INF);
    fill(ans_nd, ans_nd+N, INF);
    
    REP(i, n) cin >> d[i];

    REP(i, m) {
        int u, v; cin >> u >> v; u--, v--;
        adj[u].pb(v), adj[v].pb(u);
    }
    int k = 0;
    REP(u, n) {
        if (!vis[u]) {
            dfs(u);
            REP(i, sz[u]) {
            	cout << i << sep << dy[u][i] << endl;
            }
            // k += sz[u];
            // for(int i = k ; i >= 0 ; i --) {
                // ans_dy[i] = ans_dy[0] + min({dy[u][i], nd[u][i], (i-1 < 0 ? INF : dn[u][i-1])});
                // ans_dn[i] = ans_dn[0] + nd[u][i];
                // ans_nd[i] = ans_nd[0] + min({nd[u][i], dn[u][i], dy[u][i]});
                // for(int j = 1 ; j <= min(i, sz[u]) ; j ++) {
                    // ans_dy[i] = min(ans_dy[i], ans_dy[j] + min({dy[u][i-j], nd[u][i-j], (i-j-1 < 0 ? INF : dn[u][i-j-1])}));
                    // ans_dn[i] = min(ans_dn[i], ans_dn[j] + nd[u][i-j]);
                    // ans_nd[i] = min(ans_nd[i], ans_nd[j] + min({nd[u][i-j], dn[u][i-j], dy[u][i-j]}));
                // }
            // }
        }
    }
    // REP(i, n) {
        // ans[i] = min({ans_dy[i], ans_dn[i], ans_nd[i], INF});
    	// cout << ans[i] << sep;
    // }
    // cout << endl;
    // cin >> q;
    // while(q--) {
        // int s; cin >> s;
        // int res = upper_bound(ans, ans+n+1, s) - ans;
        // cout << res << endl;
    // }
}

// check MAXN
int32_t main() {
	fastIO;
	
	solve();
	
	return 0;
}

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