Submission #516249

#	Time	Username	Problem	Language	Result	Execution time	Memory
516249		DanerZein	Split the Attractions (IOI19_split)	C++14	0 / 100	57 ms	19640 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
const int MAX_N=2510;
vector<vi> G;
vector<ii> ab;
vector<int> res;
int n,m;
int num[MAX_N],low[MAX_N],pa[MAX_N],art[MAX_N],sb[MAX_N];
int vis[MAX_N];
int ite=0;
void dfs(int u,int p){
  sb[u]=1;
  pa[u]=p;
  low[u]=num[u]=ite; ite++;
  vis[u]=1;
  for(auto &v:G[u]){
    if(!vis[v]){
      dfs(v,u);
      sb[u]+=sb[v];
      low[u]=min(low[u],low[v]);
    }
    else{
      if(v!=p)
	low[u]=min(low[u],num[v]);
    }
  }
}
vector<int> ba,na;
int dp[MAX_N][MAX_N];
int path[MAX_N][MAX_N];
int dif,tam;
int knap(int id,int w){
  if(dp[id][w]!=-1) return dp[id][w];
  if(id==ba.size()){
    if(w<dif) return 1e9; 
    return w;
  }
  int to=knap(id+1,w+ba[id]);
  int nt=knap(id+1,w);
  path[id][w]=(to<nt);
  return dp[id][w]=min(to,nt);  
}
void abajo(int u,int col){
  if(tam==0) return;
  res[u]=col;
  tam--;
  for(auto &v:G[u]){
    if(num[u]<num[v] && !res[v]){
      abajo(v,col);
    }
    if(tam==0) return;
  }
}
void colorear(int u,int col){
  if(tam==0) return;
  res[u]=col;
  tam--;
  for(auto &v:G[u]){
    if(!res[v]) colorear(v,col);
    if(tam==0) return;
  }
}
vector<int> find_split(int nn, int a, int b, int c, vector<int> p, vector<int> q) {
  memset(vis,0,sizeof vis);
  n=nn;
  m=p.size();
  G.resize(n+1);
  res.resize(n);
  for(int i=0;i<m;i++){
    int a=p[i],b=q[i];
    G[a].push_back(b);
    G[b].push_back(a);
  }
  ab={ii(a,1),ii(b,2),ii(c,3)};
  sort(ab.begin(),ab.end());
  dfs(0,0);
  art[0]=(G[0].size()>1);
  for(int i=0;i<n;i++){
    if(sb[i]<ab[0].first) continue;
    int br=1;
    ba.clear();
    na.clear();
    for(auto &v:G[i]){
      if(pa[i]==v) continue;
      if(low[v]>num[i]){
	br+=sb[v];
      }
      else{
	ba.push_back(sb[v]);
	na.push_back(v);
      }
    }
    vector<int> to,nt;
    vector<bool> tn;
    tn.resize(na.size());
    int id;
    if(br<a){
      dif=a-br;
      for(int j=0;j<=ba.size();j++) for(int k=0;k<=dif;k++) dp[j][k]=-1; 
      knap(0,0);
      id=0;
      int w=0;
      while(id!=ba.size()){
	tn[id]=path[id][w];
	if(path[id][w]){
	  to.push_back(na[id]);
	  w+=ba[id];
	}
	else nt.push_back(na[id]);
	id++;
      }
    }
    else nt=na;
    id=0;
    int o1,o2;
    o1=-1; o2=sb[0]-sb[i];
    int ot;
    for(int j=0;j<nt.size();j++){
      if(low[nt[j]]>num[i]) o2+=sb[nt[j]];
      if(o1<sb[nt[j]]) ot=nt[j];
      o1=max(o1,sb[nt[j]]);
    }
    if(o1<o2) ot=pa[i];
    int re=max(o1,o2);
    if(re>=ab[1].first){
      res[i]=ab[0].second;
      tam=ab[0].first-1;
      for(auto &v:G[i]){
        if(pa[i]!=v && low[v]>num[i]){
	  abajo(v,ab[0].second);
	}
      }
      for(int j=0;j<to.size();j++){
	abajo(to[j],ab[0].second);
      }
      tam=ab[1].first;
      colorear(ot,ab[1].second);
      for(int j=0;j<res.size();j++){
	if(res[j]==0) res[j]=ab[2].second;
      }
      break;
    }
  }
  return res;
}

Compilation message (stderr)

split.cpp: In function 'int knap(int, int)':
split.cpp:37:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   if(id==ba.size()){
      |      ~~^~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:102:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |       for(int j=0;j<=ba.size();j++) for(int k=0;k<=dif;k++) dp[j][k]=-1;
      |                   ~^~~~~~~~~~~
split.cpp:106:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |       while(id!=ba.size()){
      |             ~~^~~~~~~~~~~
split.cpp:121:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for(int j=0;j<nt.size();j++){
      |                 ~^~~~~~~~~~
split.cpp:136:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |       for(int j=0;j<to.size();j++){
      |                   ~^~~~~~~~~~
split.cpp:141:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |       for(int j=0;j<res.size();j++){
      |                   ~^~~~~~~~~~~
split.cpp:120:9: warning: 'ot' may be used uninitialized in this function [-Wmaybe-uninitialized]
  120 |     int ot;
      |         ^~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36