Submission #1117718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117718		vjudge1	Paprike (COI18_paprike)	C++17	13 / 100	37 ms	15808 KiB

paprike

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define itn int
const int sz = 1e5 + 5;
int n,k;

vector<int> g[sz];
vector<int> par(sz);
vector<int> comp(sz);
vector<vector<int>> elem(sz);
int FIND(int a){
    return (par[a] == a ? a : par[a] = FIND(par[a]));
}

void UNION(itn a,int b){
    comp[b] += comp[a];
    par[a] = b;
    for(auto &i : elem[a])elem[b].push_back(i);
}

void solve(vector<int> &hmm){
    int cnt=0;
    int mink = 0;
    int cvb=0;
    for(int i=1;i<=n;++i){
        cnt += hmm[i];
        if(cnt > k){
            mink++;
            cnt = hmm[i];
        }
    }
    cnt = 0;
    for(int i=n;i>0;--i){
        cnt += hmm[i];
        if(cnt > k){
            cvb++;
            cnt = hmm[i];
        }
    }
    cout << min(cvb,mink);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> k;
    bool chain = 1;
    for(int i=1;i<=n;++i)par[i] = i;
    vector<pair<int,int>> sira;
    vector<int> hmm(n+1);
    vector<pair<int,int>> tp;
    int a,b;
    for(int i=1;i<=n;++i){
        cin >> hmm[i];
        elem[i].push_back(i);
        comp[i] = hmm[i];
        sira.push_back({hmm[i],i});
    }
    for(int i=1;i<n;++i){
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
        if(abs(a-b) > 1)chain = 0;
    }
    if(chain){
        solve(hmm);
        return 0;
    }
    for(int _=0;_<=n;++_){
        sort(sira.rbegin(),sira.rend());
        vector<pair<int,int>> sira2;
        vector<bool> vis(n+1);
        for(int i=0;i<sira.size();++i){
            a = FIND(sira[i].second);
            if(vis[a])continue;
            vis[a] = 1;
            vector<pair<int,int>> temp;
            for(auto &j : elem[sira[i].second]){
                for(auto &jj : g[j]){
                    b = FIND(jj);
                    if(a == b)continue;
                    temp.push_back({comp[b],b});
                }
            }
            sort(temp.begin(),temp.end());
            b = temp[0].second;
            if(comp[b] + comp[a] > k)continue;
            UNION(b,a);
        }
        vector<bool> vis2(n+1);
        sira.clear();
        for(int i=1;i<=n;++i){
            a = FIND(i);
            if(vis2[a])continue;
            sira.push_back({comp[a],a});
        }
    }
    int cnt=0;
    // for(int i=1;i<=n;++i)cout << comp[FIND(i)] << ' ';
    unordered_set<int> st;
    for(int i=1;i<=n;++i)st.insert(FIND(i));
    int maks = st.size() - 1;
    sira.clear();
    for(int i=1;i<=n;++i){
        par[i] = i;
        sira.push_back({hmm[i],i});
        comp[i] = hmm[i];
        elem[i].clear();
        elem[i].push_back(i);
    }
    for(int _=0;_<=n;++_){
        sort(sira.begin(),sira.end());
        vector<pair<int,int>> sira2;
        vector<bool> vis(n+1);
        for(int i=0;i<sira.size();++i){
            a = FIND(sira[i].second);
            if(vis[a])continue;
            vis[a] = 1;
            vector<pair<int,int>> temp;
            for(auto &j : elem[sira[i].second]){
                for(auto &jj : g[j]){
                    b = FIND(jj);
                    if(a == b)continue;
                    temp.push_back({comp[b],b});
                }
            }
            sort(temp.begin(),temp.end());
            b = temp[0].second;
            if(comp[b] + comp[a] > k)continue;
            UNION(b,a);
        }
        vector<bool> vis2(n+1);
        sira.clear();
        for(int i=1;i<=n;++i){
            a = FIND(i);
            if(vis2[a])continue;
            sira.push_back({comp[a],a});
        }
    }
    st.clear();
    for(int i=1;i<=n;++i)st.insert(FIND(i));
    cnt = st.size() - 1;
    cout << min(cnt,maks);
}

Compilation message (stderr)

paprike.cpp: In function 'int main()':
paprike.cpp:76:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(int i=0;i<sira.size();++i){
      |                     ~^~~~~~~~~~~~
paprike.cpp:118:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for(int i=0;i<sira.size();++i){
      |                     ~^~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 13 / 13
• Subtask 3: 0 / 27
• Subtask 4: 0 / 49