Submission #234315

#	Time	Username	Problem	Language	Result	Execution time	Memory
234315		aggu_01000101	Split the Attractions (IOI19_split)	C++14	0 / 100	8 ms	5120 KiB

split

#include <bits/stdc++.h>
#define mid(l, u) ((l+u)/2)
#define rchild(i) (i*2 + 2)
#define lchild(i) (i*2 + 1)
using namespace std;
int sz[100005], vis[100005], ss, rs, piv = -1, vistime = 0, rem;
bool hasBackEdge[100005], keep[100005], okvis[100005];
vector<pair<int, int>> t;
vector<int> sgive, tadj[100005], adj[100005], ans;
pair<int, int> se[100005];
/*
 9 4 2 3 10
0 1
0 2
0 3
0 4
0 6
0 8
1 7
3 7
4 5
5 6
 */
int dfs(int i){
    if(vis[i]==1) return 0;
    se[i].first = vistime++;
    vis[i] = sz[i] = 1;
    bool found = false;
    for(int j: adj[i]){
        if(vis[j]==0) tadj[i].push_back(j);
        sz[i]+=dfs(j);
        if(sz[j]>=t[0].first) found = true;
    }
    if(sz[i]>=t[0].first && !found) piv = i;
    se[i].second = vistime++;
    return sz[i];
}
bool dfs1(int i){
    if(!(se[i].first > se[piv].first && se[i].second < se[piv].second)) return true;
    if(vis[i]==1) return false;
    vis[i] = 1;
    for(int j: adj[i]) hasBackEdge[i] = dfs1(j) || hasBackEdge[i];
    return hasBackEdge[i];
}
void dfs2(int i){
    if(((ss - sz[i]) >= t[0].first) && hasBackEdge[i]){
        keep[i] = false;
        ss-=sz[i];
        rs+=sz[i];
        sgive.push_back(i);
        return;
    }
    for(int j: tadj[i]) dfs2(j);
}
void dfs3(int i, int lbl){ //assign from the remaining pile
    if(vis[i]==1 || !okvis[i] || rem==0) return;
    vis[i] = 1;
    ans[i] = lbl;
    rem--;
    for(int j: adj[i]) dfs3(j, lbl);
}
void dfs4(int i, int lbl){
    if(rem==0 || !keep[i]) return;
    ans[i] = lbl;
    okvis[i] = false;
    rem--;
    for(int j: tadj[i]) dfs4(j, lbl);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){
    t = {{a, 1}, {b, 2}, {c, 3}};
    sort(t.begin(), t.end());
    for(int i = 0;i<p.size();i++){
        adj[p[i]].push_back(q[i]);
        adj[q[i]].push_back(p[i]);
    }
    for(int i =0 ;i<n;i++){
        vis[i] = 0;
        hasBackEdge[i] = false;
        okvis[i] = true;
        ans.push_back(0);
        keep[i] = true;
    }
    dfs(0);
    for(int i =0 ;i<n;i++){
        vis[i] = 0;
    }
    dfs1(piv);
    ss = sz[piv];
    rs = n - sz[piv];
    dfs2(piv);
    if(rs<t[0].first || ss<t[0].first) return ans;
    int lblr, lbls, szr, szs;
    sgive.push_back(0);
    if(rs>=t[1].first){
        lblr = t[1].second;
        szr = t[1].first;
        lbls = t[0].second;
        szs = t[0].first;
    }
    else{
        lblr = t[0].second;
        szr = t[0].first;
        lbls = t[1].second;
        szs = t[1].first;
    }
    rem = szs;
    dfs4(piv, lbls);

    for(int i =0 ;i<n;i++){
        vis[i] = 0;
    }
    rem = szr;
    dfs3(0, lblr);
    for(int i = 0;i<n;i++){
        if(ans[i]==0) ans[i] = t[2].second;
    }
    return ans;
}
/*signed main(){
    int n, a, b, c, m;
    cin>>n>>a>>b>>c>>m;
    vector<int> p, q;
    for(int i = 0;i<m;i++){
        int u, v;
        cin>>u>>v;
        p.push_back(u);
        q.push_back(v);
    }
    vector<int> ans = find_split(n, a, b, c, p, q);
    for(int j: ans) cout<<j<<" ";
    cout<<endl;
}*/

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     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