Submission #790646

#	Time	Username	Problem	Language	Result	Execution time	Memory
790646		ezzzay	Split the Attractions (IOI19_split)	C++14	0 / 100	2 ms	4948 KiB

split

#include "split.h"
#include<bits/stdc++.h>
using namespace std;
bool vis[200005];
vector<int>v[200005];
int c=0;
int k=0;
void dfs(int a, int w){
    if(w>c){
        c=w;
        k=a;
    }
    for(int i=0;i<v[a].size();i++){
        int b=v[a][i];
        if(vis[b]==0){
            vis[b]=1;
            dfs(b,w+1);
            
        }
    }
}
vector<int>ans;
void dfs2(int a,vector<int>vec){
    if(ans.size()<vec.size()){
        ans=vec;
    }
    for(auto b:v[a]){
        if(vis[b]==0){
            vis[b]=1;
            vec.push_back(b);
            dfs2(b,vec);
            vec.pop_back();
        }
    }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    vector<int>res;
	vector<pair<int,int>>f;
	f.push_back({a,0});f.push_back({b,1});f.push_back({c,2});
	sort(f.begin(),f.end());
	for(int i=0;i<p.size();i++){
	    v[p[i]].push_back(q[i]);
	    v[q[i]].push_back(p[i]);
	}
	vis[0]=1;
    dfs(0,0);
    int x=k;
    for(int i=0;i<n;i++)vis[i]=0;
    vector<int>vec;
    vec.push_back(x);
    vis[x]=1;
    dfs2(x,vec);
    if(ans.size()<f[0].first+f[1].first){
        for(int i=0;i<n;i++)res.push_back(0);
        return res;
    }
    vector<int>A,B,C;
    int idx=f[0].second;
    int h=f[0].first;
    for(int i=0;i<n;i++)vis[i]=0;
    if(idx==0){
        for(int i=0;i<h;i++){
            A.push_back(ans[ans.size()-1]);
            vis[ans[ans.size()-1]]=1;
            ans.pop_back();
        }
    }
    else if(idx==1){
        for(int i=0;i<h;i++){
           B.push_back(ans[ans.size()-1]);
           vis[ans[ans.size()-1]]=1;
           ans.pop_back();
        }
    }
    else {
        for(int i=0;i<h;i++){
            C.push_back(ans[ans.size()-1]);
            vis[ans[ans.size()-1]]=1;
            ans.pop_back();
        }
    }
    idx=f[1].second;
    h=f[1].first;
    if(idx==0){
        for(int i=0;i<h;i++){
            A.push_back(ans[ans.size()-1]);
            vis[ans[ans.size()-1]]=1;
            ans.pop_back();
        }
    }
    else if(idx==1){
        for(int i=0;i<h;i++){
           B.push_back(ans[ans.size()-1]);
           vis[ans[ans.size()-1]]=1;
           ans.pop_back();
        }
    }
    else {
        for(int i=0;i<h;i++){
            C.push_back(ans[ans.size()-1]);
            vis[ans[ans.size()-1]]=1;
            ans.pop_back();
        }
    }
    idx=f[2].second;
    if(idx==0){
        for(int i=0;i<n;i++){
            if(vis[i]==0)A.push_back(i);
        }
    }
    else if(idx==1){
        for(int i=0;i<n;i++){
            if(vis[i]==0)B.push_back(i);
        }
    }
    else {
        for(int i=0;i<n;i++){
            if(vis[i]==0)C.push_back(i);
        }
    }
    for(int i=0;i<A.size();i++){
        res.push_back(A[i]);
    }
    
    for(int i=0;i<B.size();i++){
        res.push_back(B[i]);
    }
    
    for(int i=0;i<C.size();i++){
        res.push_back(C[i]);
    }
    return res;
}

Compilation message (stderr)

split.cpp: In function 'void dfs(int, int)':
split.cpp:13:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i=0;i<v[a].size();i++){
      |                 ~^~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:41:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i=0;i<p.size();i++){
      |              ~^~~~~~~~~
split.cpp:53:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |     if(ans.size()<f[0].first+f[1].first){
      |        ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
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 i=0;i<A.size();i++){
      |                 ~^~~~~~~~~
split.cpp:125:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for(int i=0;i<B.size();i++){
      |                 ~^~~~~~~~~
split.cpp:129:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for(int i=0;i<C.size();i++){
      |                 ~^~~~~~~~~

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