Submission #371059

#	Time	Username	Problem	Language	Result	Execution time	Memory
371059		chubyxdxd	Split the Attractions (IOI19_split)	C++17	0 / 100	1 ms	748 KiB

split

#include "split.h"
#include <bits/stdc++.h>

using namespace std;
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){
  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]){
    if(vis[i]==-1){
      dfs(i,a,b,c);
    }
  }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
  vector<int> v {a,b,c};
  sort(v.begin(),v.end());
  a=v[0];
  b=v[1];
  c=v[2];
  vector<int> ans(n,0);
  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]);
  }
  //cout<<a<<endl;
  if(a==1){
    memset(vis,-1,sizeof vis);
    dfs(0,a,b,c);
    for(auto i:B){
      ans[i]=2;
    }
    cout<<a<<endl;
    for(int i=0;i<n;i++){
      if(ans[i]==0){
	if(a>0){
	  ans[i]=1;
	  a--;
	  continue;
	}
	if(c>0){
	  ans[i]=3;
	  c--;
	}
      }
    }
  }
  memset(vis,-1,sizeof vis);
  int piv=0;
  for(int i=0;i<n;i++){
    if(G[i].size()==1)piv=i;
  }
  dfs2(piv,a,b,c);
  for(auto i:A)ans[i]=1;
  for(auto i:B)ans[i]=2;
  for(auto i:C)ans[i]=3;
  return ans;
  
}

Compilation message (stderr)

split.cpp: In function 'void dfs(int, int, int, int)':
split.cpp:13:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   13 |   if(B.size()==b)return;
      |      ~~~~~~~~^~~
split.cpp:17:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   17 |       if(B.size()==b)return;
      |          ~~~~~~~~^~~
split.cpp: In function 'void dfs2(int, int, int, int)':
split.cpp:22:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |   if(A.size()<a){
      |      ~~~~~~~~^~
split.cpp:26:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |     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:48:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for(int i=0;i<p.size();i++){
      |               ~^~~~~~~~~

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