oj.uz

Submission #143368

# Submission time Handle Problem Language Result Execution time Memory
143368 2019-08-13T20:58:31 Z Bench0310 Split the Attractions (IOI19_split) C++14
40 / 100
 179 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<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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 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 8 ms 8184 KB ok, correct split
5 Correct 8 ms 8184 KB ok, correct split
6 Correct 8 ms 8184 KB ok, correct split
7 Correct 150 ms 22780 KB ok, correct split
8 Correct 119 ms 20984 KB ok, correct split
9 Correct 179 ms 20344 KB ok, correct split
10 Correct 130 ms 23032 KB ok, correct split
11 Correct 151 ms 23084 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8184 KB ok, correct split
2 Correct 10 ms 8232 KB ok, correct split
3 Correct 10 ms 8184 KB ok, correct split
4 Correct 149 ms 21116 KB ok, correct split
5 Correct 115 ms 17056 KB ok, correct split
6 Correct 133 ms 23088 KB ok, correct split
7 Correct 134 ms 20728 KB ok, correct split
8 Correct 167 ms 18852 KB ok, correct split
9 Correct 120 ms 16972 KB ok, correct split
10 Correct 87 ms 18004 KB ok, correct split
11 Correct 88 ms 18136 KB ok, correct split
12 Correct 95 ms 18260 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8184 KB ok, correct split
2 Correct 150 ms 17072 KB ok, correct split
3 Correct 46 ms 11768 KB ok, correct split
4 Correct 8 ms 8184 KB ok, correct split
5 Correct 135 ms 18952 KB ok, correct split
6 Correct 141 ms 18680 KB ok, correct split
7 Correct 130 ms 18680 KB ok, correct split
8 Correct 125 ms 19704 KB ok, correct split
9 Correct 121 ms 18780 KB ok, correct split
10 Correct 37 ms 11128 KB ok, no valid answer
11 Correct 53 ms 12664 KB ok, no valid answer
12 Correct 114 ms 17736 KB ok, no valid answer
13 Correct 123 ms 17188 KB ok, no valid answer
14 Correct 114 ms 18132 KB ok, no valid answer

Subtask #4
0 / 24.0

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

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 9 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 8 ms 8184 KB ok, correct split
5 Correct 8 ms 8184 KB ok, correct split
6 Correct 8 ms 8184 KB ok, correct split
7 Correct 150 ms 22780 KB ok, correct split
8 Correct 119 ms 20984 KB ok, correct split
9 Correct 179 ms 20344 KB ok, correct split
10 Correct 130 ms 23032 KB ok, correct split
11 Correct 151 ms 23084 KB ok, correct split
12 Correct 8 ms 8184 KB ok, correct split
13 Correct 10 ms 8232 KB ok, correct split
14 Correct 10 ms 8184 KB ok, correct split
15 Correct 149 ms 21116 KB ok, correct split
16 Correct 115 ms 17056 KB ok, correct split
17 Correct 133 ms 23088 KB ok, correct split
18 Correct 134 ms 20728 KB ok, correct split
19 Correct 167 ms 18852 KB ok, correct split
20 Correct 120 ms 16972 KB ok, correct split
21 Correct 87 ms 18004 KB ok, correct split
22 Correct 88 ms 18136 KB ok, correct split
23 Correct 95 ms 18260 KB ok, correct split
24 Correct 8 ms 8184 KB ok, correct split
25 Correct 150 ms 17072 KB ok, correct split
26 Correct 46 ms 11768 KB ok, correct split
27 Correct 8 ms 8184 KB ok, correct split
28 Correct 135 ms 18952 KB ok, correct split
29 Correct 141 ms 18680 KB ok, correct split
30 Correct 130 ms 18680 KB ok, correct split
31 Correct 125 ms 19704 KB ok, correct split
32 Correct 121 ms 18780 KB ok, correct split
33 Correct 37 ms 11128 KB ok, no valid answer
34 Correct 53 ms 12664 KB ok, no valid answer
35 Correct 114 ms 17736 KB ok, no valid answer
36 Correct 123 ms 17188 KB ok, no valid answer
37 Correct 114 ms 18132 KB ok, no valid answer
38 Correct 8 ms 8184 KB ok, correct split
39 Correct 9 ms 8312 KB ok, no valid answer
40 Correct 8 ms 8184 KB ok, correct split
41 Correct 8 ms 8184 KB ok, correct split
42 Correct 9 ms 8184 KB ok, correct split
43 Correct 9 ms 8184 KB ok, correct split
44 Incorrect 9 ms 8184 KB invalid split: #1=3, #2=4, #3=5
45 Halted 0 ms 0 KB -