Submission #516267

#	Time	Username	Problem	Language	Result	Execution time	Memory
516267		DanerZein	Split the Attractions (IOI19_split)	C++14	0 / 100	60 ms	17868 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 colorear(int u,int col,bool sw){
  if(tam==0) return;
  res[u]=col;
  tam--;
  for(auto &v:G[u]){
    if((sw || num[u]<num[v]) && !res[v]){
      colorear(v,col,sw);
    }
  }
}
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);
  for(int i=1;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;
    int id;
    if(br<ab[0].first){
      dif=ab[0].first-br;
      for(int j=0;j<=ba.size();j++) for(int k=0;k<=n;k++) dp[j][k]=-1; 
      knap(0,0);
      id=0;
      int w=0;
      while(id!=ba.size()){
	if(path[id][w]){
	  to.push_back(na[id]);
	  w+=ba[id];
	}
	else nt.push_back(na[id]);
	id++;
      }
    }
    else nt=na;
    int re=sb[0]-sb[i];
    int ot;
    for(int j=0;j<nt.size();j++){
      re+=sb[nt[j]];
    }
    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]){
	  colorear(v,ab[0].second,0);
	}
      }
      for(int j=0;j<to.size();j++){
	colorear(to[j],ab[0].second,0);
      }
      tam=ab[1].first;
      for(int j=0;j<n;j++){
	if(res[j]!=0) continue;
	colorear(0,ab[1].second,1);
	if(tam==0) break;
      }
      
      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:89:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |       for(int j=0;j<=ba.size();j++) for(int k=0;k<=n;k++) dp[j][k]=-1;
      |                   ~^~~~~~~~~~~
split.cpp:93:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |       while(id!=ba.size()){
      |             ~~^~~~~~~~~~~
split.cpp:105:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(int j=0;j<nt.size();j++){
      |                 ~^~~~~~~~~~
split.cpp:116:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |       for(int j=0;j<to.size();j++){
      |                   ~^~~~~~~~~~
split.cpp:126:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |       for(int j=0;j<res.size();j++){
      |                   ~^~~~~~~~~~~
split.cpp:104:9: warning: unused variable 'ot' [-Wunused-variable]
  104 |     int ot;
      |         ^~

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