제출 #841041

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
841041		MrBrionix	봉쇄 시간 (IOI23_closing)	C++17	8 / 100	1063 ms	37436 KiB

closing

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

const int MAXN = 200'001;
vector<pair<int,long long>> grafo[MAXN];
long long dist[MAXN][2];

void dfs(int nodo,int last,long long val,int mode){
    dist[nodo][mode]=val;
    
    for(auto [to,cost] : grafo[nodo]){
        if(to!=last){
            dfs(to,nodo,val+cost,mode);
        }
    }
}

bool a[MAXN][2],due[MAXN];

bool dfs2(int nodo,int last,int mode){
    bool flag=due[nodo];
    
    for(auto [i,cost] : grafo[nodo]){
        if(i!=last){
            flag|=dfs2(i,nodo,mode);
        }
    }
    
    if(flag)a[nodo][mode]=true;
    return flag;
}

int max_score(int N, int X, int Y, long long K,
    std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    for(int i=0;i<=N;i++)grafo[i].clear();
    
    for(int i=0;i<N-1;i++){
        grafo[U[i]].push_back({V[i],W[i]});
        grafo[V[i]].push_back({U[i],W[i]});
    }
    if(X>Y)swap(X,Y);
    
    dfs(X,-1,0,0);
    dfs(Y,-1,0,1);
    /*
    int ans=0;
    vector<long long> opz;
    for(int i=0;i<N;i++){
        opz.push_back(min(dist[i][0],dist[i][1]));
    }
    sort(opz.begin(),opz.end());
    
    long long tmp = K;
    for(int i=0;i<opz.size();i++){
        if(tmp>=opz[i]){
            ans++;
            tmp-=opz[i];
        }else break;
    }
    
    
    for(int l=0;l<N;l++){
        for(int r=l;r<N;r++){
            long long curr=0;
            for(int i=l;i<=r;i++){
                curr+=max(dist[i][0],dist[i][1]);
            }
            
            for(int i=X;i<l;i++){
                curr+=dist[i][0];
            }
            for(int i=r+1;i<=Y;i++){
                curr+=dist[i][1];
            }
            
            int ind1=min(X-1,l-1),ind2=max(Y+1,r+1);
            long long tmp = K-curr;
            //cout<<l<<" "<<r<<" "<<tmp<<"\n";
            
            if(tmp<0)continue;
            while((ind1>=0 && dist[ind1][0]<=tmp) || (ind2<N && dist[ind2][1]<=tmp)){
                if(ind1<0){
                    tmp-=dist[ind2][1];
                    ind2++;
                }else if(ind2>=N){
                    tmp-=dist[ind1][0];
                    ind1--;
                }else if(dist[ind1][0]<dist[ind2][1]){
                    tmp-=dist[ind1][0];
                    ind1--;
                }else{
                    tmp-=dist[ind2][1];
                    ind2++;
                }
            }
            
            ans=max(ans,ind2-ind1-1+(r-l+1));
        }
    }
    return ans;
     */
    
    int ans=0;
    for(int i=(1<<N)-1;i>=0;i--){
        memset(a,false,sizeof(a));
        memset(due,false,sizeof(due));
        
        long long s=0;
        int cc=0;
        for(int j=0;j<N;j++){
            if(i&(1<<j)){
                due[j]=true;
                s+=max(dist[j][0],dist[j][1]);
                cc+=2;
            }else cc++;
        }
        if(s>K || cc<ans)continue;
        
        dfs2(X,-1,0);
        dfs2(Y,-1,1);
        
        long long tmp = K;
        int curr=0;
        vector<long long> opz;
        for(int j=0;j<N;j++){
            if(a[j][0] && a[j][1]){
                tmp-=max(dist[j][0],dist[j][1]);
                curr+=2;
            }else if(a[j][0]){
                tmp-=dist[j][0];
                curr++;
            }else if(a[j][1]){
                tmp-=dist[j][1];
                curr++;
            }else{
                opz.push_back(min(dist[j][0],dist[j][1]));
            }
            if(tmp<0)break;
        }
        sort(opz.begin(),opz.end());
        if(tmp<0)continue;
        for(int j=0;j<opz.size();j++){
            if(tmp>=opz[j]){
                tmp-=opz[j];
                curr++;
            }
        }
        ans=max(ans,curr);
    }
    
    return ans;
    /*
    vector<long long> opz;
    for(int i=0;i<N;i++){
        opz.push_back(min(dist[i][0],dist[i][1]));
    }
    sort(opz.begin(),opz.end());
    
    int ans=0;
    for(int i=0;i<opz.size();i++){
        if(K>=opz[i]){
            ans++;
            K-=opz[i];
        }else break;
    }
    
      return ans;*/
}

/*
  2
  7 0 2 10
  0 1 2
  0 3 3
  1 2 4
  2 4 2
  2 5 5
  5 6 3
  4 0 3 20
  0 1 18
  1 2 1
  2 3 19
 
 
int main()
{
    
    int Q;
    assert(1 == scanf("%d", &Q));
    
    std::vector<int> N(Q), X(Q), Y(Q);
    std::vector<long long> K(Q);
    std::vector<std::vector<int>> U(Q), V(Q), W(Q);
    
    for (int q = 0; q < Q; q++)
    {
        assert(4 == scanf("%d %d %d %lld", &N[q], &X[q], &Y[q], &K[q]));
        
        U[q].resize(N[q] - 1);
        V[q].resize(N[q] - 1);
        W[q].resize(N[q] - 1);
        for (int i = 0; i < N[q] - 1; ++i)
        {
            assert(3 == scanf("%d %d %d", &U[q][i], &V[q][i], &W[q][i]));
        }
    }
    fclose(stdin);
    
    std::vector<int> result(Q);
    for (int q = 0; q < Q; q++)
    {
        result[q] = max_score(N[q], X[q], Y[q], K[q], U[q], V[q], W[q]);
    }
    
    for (int q = 0; q < Q; q++)
    {
        printf("%d\n", result[q]);
    }
    fclose(stdout);
    
    return 0;
}
*/

컴파일 시 표준 에러 (stderr) 메시지

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:143:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |         for(int j=0;j<opz.size();j++){
      |                     ~^~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17