Submission #705672

#	Time	Username	Problem	Language	Result	Execution time	Memory
705672		new_acc	Split the Attractions (IOI19_split)	C++14	100 / 100	148 ms	30320 KiB

split

#include "split.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=2e5+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e16;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
int pod[N],o[N];
pair<int,int> t[3];
vi graf[N],drzewo[N],cr,res;
bool vis[N],vis2[N];
void dfs(int v){
    vis[v]=1;
    pod[v]=1;
    for(auto u:graf[v]){
        if(vis[u]) continue;
        drzewo[v].push_back(u);
        dfs(u);
        o[u]=v;
        pod[v]+=pod[u];
    }
}
void dfs2(int v){
    vis[v]=1;
    cr.push_back(v);
    for(auto u:drzewo[v]){
        dfs2(u);
    }
}
void dfs4(int v){
    vis[v]=1;
    cr.push_back(v);
    for(auto u:graf[v]){
        if(vis[u]) continue;
        dfs4(u);
    }
}
int dfs3(int v,int zos){
    if(zos==0) return 0; 
    vis[v]=1;
    if(!vis2[v]){
        zos--;
        res[v-1]=t[0].se;
    }
    for(auto u:graf[v]){
        if(vis[u] or (!vis2[v] and vis2[u])) continue;
        zos=dfs3(u,zos);
    }
    return zos;
}
int centroid(int v,int n){
    for(auto u:drzewo[v]){
        if(pod[u]*2>n)
            return centroid(u,n);
    }
    return v;
}
vi find_split(int n,int a,int b,int cc,vi p,vi q){
    for(int i=0;i<n;i++) res.push_back(0);
    t[0]={a,1},t[1]={b,2},t[2]={cc,3};
    sort(t,t+3);
    for(int i=0;i<p.size();i++){
        int u=p[i],v=q[i];
        u++,v++;
        graf[u].push_back(v),graf[v].push_back(u);
    } 
    dfs(1);
    /*cout<<"\n";
    for(int i=1;i<=n;i++){
        for(auto u:drzewo[i]) cout<<i-1<<" "<<u-1<<"\n";
    }
    exit(0);*/
    for(int i=1;i<=n;i++) vis[i]=0;
    int c=centroid(1,n);
    vector<vi> niz;
    for(auto u:drzewo[c]){
        dfs2(u);
        niz.push_back(cr);
        cr.clear();
    }
    vi ost;
    vis[c]=1;
    if(c!=1){
        dfs4(o[c]);
        niz.push_back(cr);
    }
    for(int i=1;i<=n;i++) vis[i]=0;
    int g=-1;
    for(int i=0;i<niz.size();i++){
        if(niz[i].size()>=t[0].fi){
            g=i;
            for(int i2=0;i2<t[0].fi;i2++)
                res[niz[i][i2]-1]=t[0].se;
            break;
        }
    }
    if(g!=-1){
        res[c-1]=t[1].se;
        t[1].fi--;
        for(int i=0;i<niz.size();i++){
            if(i==g) continue;
            for(int i2=0;i2<niz[i].size() and t[1].fi>0;t[1].fi--,i2++)
                res[niz[i][i2]-1]=t[1].se;
        }
        for(int i=0;i<n;i++)
            if(res[i]==0) res[i]=t[2].se;
        return res;
    }
    if(c==1) return res;
    int sum=t[0].fi;
    for(auto u:niz[niz.size()-1]) res[u-1]=t[0].se,vis2[u]=1,sum--;
    vis[c]=1;
    if(dfs3(o[c],sum)){
        for(auto &u:res) u=0;
        return res;
    }
    res[c-1]=t[1].se;
    t[1].fi--;
    for(auto u:niz){
        bool ok=1;
        for(int i=0;i<u.size();i++){
            if(vis[u[i]]) ok=0;
        }
        if(!ok) continue;
        for(int i=0;i<u.size() and t[1].fi>0;t[1].fi--,i++){
            res[u[i]-1]=t[1].se;
        }
    }
    for(int i=0;i<n;i++) 
        if(!res[i]) res[i]=t[2].se;
    return res;
}
/*int main(){
    int n,a,b,c,m;
    cin>>n>>m>>a>>b>>c;
    vi p,q;
    for(int a,b,i=1;i<=m;i++){
        cin>>a>>b;
        p.push_back(a),q.push_back(b);
    }
    vi ans=find_split(n,a,b,c,p,q);
    return 0;
    for(auto u:ans) cout<<u<<" ";
    cout<<"\n";
}*/

Compilation message (stderr)

split.cpp: In function 'vi find_split(int, int, int, int, vi, vi)':
split.cpp:75:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i=0;i<p.size();i++){
      |                 ~^~~~~~~~~
split.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i=0;i<niz.size();i++){
      |                 ~^~~~~~~~~~~
split.cpp:103:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  103 |         if(niz[i].size()>=t[0].fi){
      |                         ^
split.cpp:113:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |         for(int i=0;i<niz.size();i++){
      |                     ~^~~~~~~~~~~
split.cpp:115:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |             for(int i2=0;i2<niz[i].size() and t[1].fi>0;t[1].fi--,i2++)
      |                          ~~^~~~~~~~~~~~~~
split.cpp:134:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |         for(int i=0;i<u.size();i++){
      |                     ~^~~~~~~~~
split.cpp:138:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         for(int i=0;i<u.size() and t[1].fi>0;t[1].fi--,i++){
      |                     ~^~~~~~~~~

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