oj.uz

Submission #143367

# Submission time Handle Problem Language Result Execution time Memory
143367 2019-08-13T20:55:06 Z Bench0310 Split the Attractions (IOI19_split) C++14
11 / 100
 162 ms 23088 KB 
#include <bits/stdc++.h>

using namespace std;

int n;
const int N=100000;
vector<int> v[N];
vector<int> g[N];
vector<int> z[N];
vector<int> d;
vector<int> sub(N,0);
vector<int> id(N);
vector<bool> vis(N,0);
vector<int> res;

void dfs1(int a)
{
    sub[a]=1;
    for(int to:v[a])
    {
        if(sub[to]!=0) continue;
        g[a].push_back(to);
        g[to].push_back(a);
        dfs1(to);
        sub[a]+=sub[to];
    }
}

int get_centroid(int a,int p=-1)
{
    for(int to:g[a])
    {
        if(to!=p&&sub[to]>n/2) return get_centroid(to,a);
    }
    return a;
}

void dfs2(int a,int now)
{
    sub[a]=1;
    id[a]=now;
    for(int to:g[a])
    {
        if(sub[to]!=0) continue;
        if(now==-1) d.push_back(to);
        dfs2(to,(now!=-1?now:to));
        sub[a]+=sub[to];
    }
}

void solve_one(vector<int> src,int num,int t,int centroid)
{
    vector<bool> pos(n,0);
    for(int a:src) pos[a]=1;
    queue<int> q;
    q.push(src[0]);
    while(num>0)
    {
        int e=q.front();
        q.pop();
        res[e]=t;
        num--;
        for(int to:v[e]) if(to!=centroid&&pos[id[to]]==1&&res[to]==0) q.push(to);
    }
}

void solve_two(int num,int t,int centroid)
{
    res[centroid]=t;
    num--;
    queue<int> q;
    for(int to:g[centroid]) if(res[to]==0) q.push(to);
    while(num>0)
    {
        int e=q.front();
        q.pop();
        res[e]=t;
        num--;
        for(int to:g[e]) if(res[to]==0) q.push(to);
    }
}

void solve_three(int t)
{
    for(int i=0;i<n;i++) if(res[i]==0) res[i]=t;
}

vector<int> component(int src,int a)
{
    vector<int> comp;
    int cnt=0;
    vis[src]=1;
    queue<int> q;
    q.push(src);
    while(!q.empty())
    {
        int e=q.front();
        q.pop();
        cnt+=sub[e];
        comp.push_back(e);
        if(cnt>=a) break;
        for(int to:z[e])
        {
            if(vis[to]) continue;
            vis[to]=1;
            q.push(to);
        }
    }
    if(cnt>=a) return comp;
    else return {-1};
}

vector<int> find_split(int _n,int a,int b,int c,vector<int> ca,vector<int> cb)
{
    n=_n;
    res.resize(n,0);
    int m=ca.size();
    for(int i=0;i<m;i++)
    {
        v[ca[i]].push_back(cb[i]);
        v[cb[i]].push_back(ca[i]);
    }
    dfs1(0);
    int centroid=get_centroid(0);
    for(int i=0;i<n;i++) sub[i]=0;
    dfs2(centroid,-1);
    vector<pair<int,int>> abc={{a,1},{b,2},{c,3}};
    sort(abc.begin(),abc.end());
    for(int i=0;i<n;i++)
    {
        if(i!=centroid&&sub[i]>=abc[0].first)
        {
            solve_one({i},abc[0].first,abc[0].second,centroid);
            solve_two(abc[1].first,abc[1].second,centroid);
            solve_three(abc[2].second);
            return res;
        }
    }
    for(int i=0;i<m;i++)
    {
        if(ca[i]==centroid||cb[i]==centroid) continue;
        if(id[ca[i]]!=id[cb[i]])
        {
            z[id[ca[i]]].push_back(id[cb[i]]);
            z[id[cb[i]]].push_back(id[ca[i]]);
        }
    }
    for(int to:d)
    {
        if(vis[to]) continue;
        vector<int> comp=component(to,abc[0].first);
        if(comp[0]==-1) continue;
        solve_one(comp,abc[0].first,abc[0].second,centroid);
        solve_two(abc[1].first,abc[1].second,centroid);
        solve_three(abc[2].second);
        return res;
    }
    return res;
}

/*int main()
{
    vector<int> temp=find_split(9, 4, 2, 3, {0, 0, 0, 0, 0, 0, 1, 3, 4, 5},{1, 2, 3, 4, 6, 8, 7, 7, 5, 6});
    for(int a:temp) cout << a << " ";
    return 0;
}
*/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8184 KB ok, correct split
2 Correct 8 ms 8184 KB ok, correct split
3 Correct 8 ms 8184 KB ok, correct split
4 Correct 9 ms 8184 KB ok, correct split
5 Correct 9 ms 8188 KB ok, correct split
6 Incorrect 8 ms 8184 KB invalid split: #1=40, #2=2, #3=58
7 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8200 KB ok, correct split
2 Correct 8 ms 8184 KB ok, correct split
3 Correct 8 ms 8180 KB ok, correct split
4 Correct 151 ms 20868 KB ok, correct split
5 Correct 120 ms 17032 KB ok, correct split
6 Correct 141 ms 23088 KB ok, correct split
7 Correct 129 ms 20816 KB ok, correct split
8 Correct 162 ms 18808 KB ok, correct split
9 Correct 121 ms 16988 KB ok, correct split
10 Correct 95 ms 18124 KB ok, correct split
11 Correct 118 ms 18000 KB ok, correct split
12 Correct 92 ms 18104 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8184 KB ok, correct split
2 Correct 138 ms 17116 KB ok, correct split
3 Incorrect 45 ms 11768 KB invalid split: #1=2, #2=66, #3=40032
4 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8184 KB ok, correct split
2 Correct 8 ms 8184 KB ok, no valid answer
3 Correct 9 ms 8192 KB ok, correct split
4 Correct 8 ms 8184 KB ok, correct split
5 Incorrect 8 ms 8184 KB invalid split: #1=10, #2=2, #3=4
6 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8184 KB ok, correct split
2 Correct 8 ms 8184 KB ok, correct split
3 Correct 8 ms 8184 KB ok, correct split
4 Correct 9 ms 8184 KB ok, correct split
5 Correct 9 ms 8188 KB ok, correct split
6 Incorrect 8 ms 8184 KB invalid split: #1=40, #2=2, #3=58
7 Halted 0 ms 0 KB -