Submission #371095

#	Time	Username	Problem	Language	Result	Execution time	Memory
371095		chubyxdxd	Split the Attractions (IOI19_split)	C++17	40 / 100	167 ms	15996 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define sc second
#define ff first
using namespace std;
typedef pair<int,int> ii;
vector<vector<int>> G;
vector<int> A;
vector<int> B;
vector<int> C;
int vis[100010];
void dfs(int node,int a,int b,int c){
  vis[node]=1;
  B.push_back(node);
  if(B.size()==b)return;
  for(auto i:G[node]){
    if(vis[i]==-1){
      dfs(i,a,b,c);
      if(B.size()==b)return;
    }
  }
}
void dfs2(int node,int a,int b,int c){
  //cout<<node<<endl;
  if(A.size()<a){
    A.push_back(node);
  }
  else{
    if(B.size()<b){
      B.push_back(node);
    }
    else{
      C.push_back(node);
    }
  }
  vis[node]=1;
  for(auto i:G[node]){
    //cout<<i<<" ";
    if(vis[i]==-1){
      dfs2(i,a,b,c);
    }
  }
  //cout<<endl;
}
int sz[100010];
int N;
int dfsz(int node,int pad){
  sz[node]=1;
  vis[node]=1;
  for(auto i:G[node]){
    if(vis[i]!=-1)continue;
    sz[node]+=dfsz(i,node);
  }
  return sz[node];
}
int piv=-1,an=-1;
vector<int> ans;
void dfsfind(int node,int pad,int a,int b){
  //cout<<node<<" "<<sz[node]<<endl;
  vis[node]=1;
  if(sz[node]>=a && N-sz[node]>=b){
    piv=node;an=pad;
    return;
  }
  if(sz[node]>=b && N-sz[node]>=a){
    piv=pad;an=node;
    return;
  }
  for(auto i:G[node]){
    if(vis[i]!=-1)continue;
    dfsfind(i,node,a,b);
  }
}
int cnt=0;
void dfs1(int node,int pad,int a,int col){
  cnt++;
  vis[pad]=1;
  vis[node]=1;
  if(cnt<=a){
    ans[node]=col;
  }
  for(auto i:G[node]){
    if(vis[i]!=-1)continue;
    dfs1(i,node,a,col);
  }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
  N=n;
  ans.assign(n,0);
  vector<ii> v{ii(a,1),ii(b,2),ii(c,3)};
  sort(v.begin(),v.end());
  G.assign(n+5,vector<int>());
  for(int i=0;i<p.size();i++){
    G[p[i]].push_back(q[i]);
    G[q[i]].push_back(p[i]);
  }
  memset(vis,-1,sizeof vis);
  int h=dfsz(0,0);
  memset(vis,-1,sizeof vis);
   dfsfind(0,0,v[0].ff,v[1].ff);
   if(piv==-1 && an==-1)return ans;
   cnt=0;
   //cout<<piv<<" "<<an<<endl;
   memset(vis,-1,sizeof vis);
   dfs1(piv,an,v[0].ff,v[0].sc);
   memset(vis,-1,sizeof vis);
   cnt=0;
   dfs1(an,piv,v[1].ff,v[1].sc);
   for(int i=0;i<n;i++){
     if(ans[i]==0){
       ans[i]=v[2].sc;
     }}
   return ans; 
}

Compilation message (stderr)

split.cpp: In function 'void dfs(int, int, int, int)':
split.cpp:15:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   15 |   if(B.size()==b)return;
      |      ~~~~~~~~^~~
split.cpp:19:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   19 |       if(B.size()==b)return;
      |          ~~~~~~~~^~~
split.cpp: In function 'void dfs2(int, int, int, int)':
split.cpp:25:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |   if(A.size()<a){
      |      ~~~~~~~~^~
split.cpp:29:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |     if(B.size()<b){
      |        ~~~~~~~~^~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:93:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   for(int i=0;i<p.size();i++){
      |               ~^~~~~~~~~
split.cpp:98:7: warning: unused variable 'h' [-Wunused-variable]
   98 |   int h=dfsz(0,0);
      |       ^

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