Submission #423293

#	Time	Username	Problem	Language	Result	Execution time	Memory
423293		DanerZein	Power Plant (JOI20_power)	C++14	6 / 100	1580 ms	332 KiB

power

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
vector<vi> G;
string x;
set<int> br;
bool dfs(int u,int p,int b){
  for(auto &v:G[u]){
    if(v==b) return 1;
    if(v!=p){
      if(dfs(v,u,b)){
	if(x[v]=='1') br.insert(v);
	return 1;
      }
    }
  }
  return 0;
}
int main(){
  int n;
  cin>>n;
  G.resize(n+1);
  for(int i=0;i<n-1;i++){
    int a,b; cin>>a>>b;
    a--; b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  cin>>x;
  int rp=-1;
  for(int i=0;i<(1<<n);i++){
    //cout<<i<<endl;
    vector<int> po;
    int c=0;
    for(int j=0;j<n;j++){
      if(i&(1<<j) && x[j]=='1'){
	c++;
	po.push_back(j);
      }
    }
    br.clear();
    for(int j=0;j<po.size();j++){
      for(int k=j+1;k<po.size();k++){
	dfs(po[j],-1,po[k]);
      }
    }
    for(int j=0;j<po.size();j++){
      if(br.find(po[j])!=br.end()) c--;
    }
    rp=max(rp,c-(int)br.size());
  }
  cout<<rp<<endl;
}

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int j=0;j<po.size();j++){
      |                 ~^~~~~~~~~~
power.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |       for(int k=j+1;k<po.size();k++){
      |                     ~^~~~~~~~~~
power.cpp:48:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int j=0;j<po.size();j++){
      |                 ~^~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 0 / 41
• Subtask 3: 0 / 53