Submission #569727

#	Time	Username	Problem	Language	Result	Execution time	Memory
569727		losmi247	The Xana coup (BOI21_xanadu)	C++14	0 / 100	104 ms	57340 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =1e5+4;

int n;
vector <int> g[N];
int on[N];
ll dp[N][2][2]; /// i-ti cvor, j-da li je upaljen ili ne,k-da li je na njemu izvrsena operacija ili ne

bool cmp1(pair <ll,ll> x,pair <ll,ll> y){
    return (x.second-x.first < y.second-y.first);
}

bool cmp2(pair <ll,ll> x,pair <ll,ll> y){
    return (x.first-x.second < y.first-y.second);
}

void dfs(int x,int par){
    if(g[x].size() == 1 && x != 1){
        if(on[x]){
            dp[x][1][0] = 0;
            dp[x][0][1] = 1;
        }
        else{
            dp[x][0][0] = 0;
            dp[x][1][1] = 1;
        }
        /*cout << "postavio " << x << endl;
        cout << dp[x][0][0] << " " << dp[x][0][1] << " " << dp[x][1][0] << " " << dp[x][1][1] << endl;*/
        return;
    }

    for(auto f : g[x]){
        if(f == par) continue;
        dfs(f,x);
    }

    /// svi vec ugaseni tj dp[child][0][0/1]
    vector <pair<ll,ll>> vdole,vgore,v;
    for(auto f : g[x]){
        if(f == par) continue;
        if(dp[f][0][1] < dp[f][0][0]) vgore.push_back({dp[f][0][1],dp[f][0][0]}); /// nagore
        else vdole.push_back({dp[f][0][1],dp[f][0][0]}); /// nadole
    }
    if(!vgore.empty()) for(auto f : vgore) v.push_back(f);
    if(!vdole.empty()) for(auto f : vdole) v.push_back(f);

    /*for(auto f : vgore) cout << f.first << " a " << f.second << endl;
    cout << endl;
    for(auto f : vdole) cout << f.first << " b " << f.second << endl;
    cout << endl;*/

    /// pokusaj parno ili neparno keceva
    ll sumgore = 0,sumdole = 0;
    if(!vgore.empty()) for(auto f : vgore) sumgore += f.first;
    if(!vdole.empty()) for(auto f : vdole) sumdole += f.second;

    vector <pair<ll,ll>> vgoresrt = vgore;
    if(!vgoresrt.empty()) sort(vgoresrt.begin(),vgoresrt.end(),cmp1);
    vector <ll> vgsvalfr(vgoresrt.size()+1,0),vgsvalsc(vgoresrt.size()+1,0);
    if(!vgoresrt.empty()){
        vgsvalsc[0] = vgoresrt[0].second;
        vgsvalfr[0] = vgoresrt[0].first;
        for(int i = 1; i < vgoresrt.size(); i++){
            vgsvalfr[i] = vgsvalfr[i-1]+vgoresrt[i].first;
            vgsvalsc[i] = vgsvalsc[i-1]+vgoresrt[i].second;
        }
    }

    vector <pair<ll,ll>> vdolesrt = vdole;
    if(!vdolesrt.empty()) sort(vdolesrt.begin(),vdolesrt.end(),cmp2);
    vector <ll> vdsvalfr(vdolesrt.size()+1,0),vdsvalsc(vdolesrt.size()+1,0);
    if(!vdolesrt.empty()){
        vdsvalfr[0] = vdolesrt[0].first;
        vdsvalsc[0] = vdolesrt[0].second;
        for(int i = 1; i < vdolesrt.size(); i++){
            vdsvalfr[i] = vdsvalfr[i-1]+vdolesrt[i].first;
            vdsvalsc[i] = vdsvalsc[i-1]+vdolesrt[i].second;
        }
    }

    ll minvalpar = 7e18,minvalnep = 7e18;
    for(int i = 0; i < v.size(); i++){
        ll val = 0;
        if(i < vgore.size()){
            val = sumgore+sumdole;
            if(i != vgore.size()-1) val += -vgsvalfr[vgore.size()-i-2]+vgsvalsc[vgore.size()-i-2];
        }
        else{
            val = sumgore+sumdole;
            val += -vdsvalsc[i-vgore.size()]+vdsvalfr[i-vgore.size()];
        }
        if(i&1) minvalpar = min(minvalpar,val);
        else minvalnep = min(minvalnep,val);
    }

    if(on[x]) dp[x][1][0] = min(dp[x][1][0],minvalpar);
    else dp[x][0][0] = min(dp[x][0][0],minvalpar);

    if(on[x]) dp[x][0][0] = min(dp[x][0][0],minvalnep);
    else dp[x][1][0] = min(dp[x][1][0],minvalnep);



    /// svi upaljeni tj dp[child][1][0/1]
    vdole.clear();
    vgore.clear();
    v.clear();
    vgsvalfr.clear();
    vgsvalsc.clear();
    vdsvalfr.clear();
    vdsvalsc.clear();
    for(auto f : g[x]){
        if(f == par) continue;
        if(dp[f][1][1] < dp[f][1][0]) vgore.push_back({dp[f][1][1],dp[f][1][0]}); /// nagore
        else vdole.push_back({dp[f][1][1],dp[f][1][0]}); /// nadole
    }
    if(!vgore.empty()) for(auto f : vgore) v.push_back(f);
    if(!vdole.empty()) for(auto f : vdole) v.push_back(f);

    /*for(auto f : vgore) cout << f.first << " c " << f.second << endl;
    cout << endl;
    for(auto f : vdole) cout << f.first << " d " << f.second << endl;
    cout << endl;*/

    /// pokusaj parno ili neparno keceva
    sumgore = 0,sumdole = 0;
    if(!vgore.empty()) for(auto f : vgore) sumgore += f.first;
    if(!vdole.empty()) for(auto f : vdole) sumdole += f.second;

    vgoresrt = vgore;
    if(!vgoresrt.empty()) sort(vgoresrt.begin(),vgoresrt.end(),cmp1);
    vgsvalfr.resize(vgoresrt.size()+1,0);
    vgsvalsc.resize(vgoresrt.size()+1,0);
    if(!vgoresrt.empty()){
        vgsvalsc[0] = vgoresrt[0].second;
        vgsvalfr[0] = vgoresrt[0].first;
        for(int i = 1; i < vgoresrt.size(); i++){
            vgsvalfr[i] = vgsvalfr[i-1]+vgoresrt[i].first;
            vgsvalsc[i] = vgsvalsc[i-1]+vgoresrt[i].second;
        }
    }

    vdolesrt = vdole;
    if(!vdolesrt.empty()) sort(vdolesrt.begin(),vdolesrt.end(),cmp2);
    vdsvalfr.resize(vdolesrt.size()+1,0);
    vdsvalsc.resize(vdolesrt.size()+1,0);
    if(!vdolesrt.empty()){
        vdsvalfr[0] = vdolesrt[0].first;
        vdsvalsc[0] = vdolesrt[0].second;
        for(int i = 1; i < vdolesrt.size(); i++){
            vdsvalfr[i] = vdsvalfr[i-1]+vdolesrt[i].first;
            vdsvalsc[i] = vdsvalsc[i-1]+vdolesrt[i].second;
        }
    }

    minvalpar = 7e18,minvalnep = 7e18;
    for(int i = 0; i < v.size(); i++){
        ll val = 0;
        if(i < vgore.size()){
            val = sumgore+sumdole;
            if(i != vgore.size()-1) val += -vgsvalfr[vgore.size()-i-2]+vgsvalsc[vgore.size()-i-2];
        }
        else{
            val = sumgore+sumdole;
            val += -vdsvalsc[i-vgore.size()]+vdsvalfr[i-vgore.size()];
        }
        if(i&1) minvalpar = min(minvalpar,val);
        else minvalnep = min(minvalnep,val);
    }

    if(on[x]) dp[x][0][1] = min(dp[x][0][1],minvalpar);
    else dp[x][1][1] = min(dp[x][1][1],minvalpar);

    if(on[x]) dp[x][1][1] = min(dp[x][1][1],minvalnep);
    else dp[x][0][1] = min(dp[x][0][1],minvalnep);

    //cout << "kraj " << x << " " << dp[x][0][0] << " " << dp[x][0][1] << " " << dp[x][1][0] << " " << dp[x][1][1] << endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i < n; i++){
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 1; i <= n; i++){
        cin >> on[i];
    }

    for(int i = 1; i <= n; i++){
        dp[i][0][0] = dp[i][0][1] = dp[i][1][0] = dp[i][1][1] = 1e9;
    }
    dfs(1,0);

    ll sol = min(dp[1][0][0],dp[1][0][1]);
    if(sol >= 1e9) cout << "impossible" << endl;
    else if(dp[1][0][0] < dp[1][0][1]) cout << dp[1][0][0] << endl;
    else cout << dp[1][0][1]+1 << endl;
}

Compilation message (stderr)

xanadu.cpp: In function 'void dfs(int, int)':
xanadu.cpp:65:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(int i = 1; i < vgoresrt.size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~~
xanadu.cpp:77:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for(int i = 1; i < vdolesrt.size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~~
xanadu.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
xanadu.cpp:86:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         if(i < vgore.size()){
      |            ~~^~~~~~~~~~~~~~
xanadu.cpp:88:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |             if(i != vgore.size()-1) val += -vgsvalfr[vgore.size()-i-2]+vgsvalsc[vgore.size()-i-2];
      |                ~~^~~~~~~~~~~~~~~~~
xanadu.cpp:139:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |         for(int i = 1; i < vgoresrt.size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~~
xanadu.cpp:152:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |         for(int i = 1; i < vdolesrt.size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~~
xanadu.cpp:159:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
xanadu.cpp:161:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |         if(i < vgore.size()){
      |            ~~^~~~~~~~~~~~~~
xanadu.cpp:163:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |             if(i != vgore.size()-1) val += -vgsvalfr[vgore.size()-i-2]+vgsvalsc[vgore.size()-i-2];
      |                ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 40
• Subtask 5: 0 / 30