oj.uz

Submission #143386

# Submission time Handle Problem Language Result Execution time Memory
143386 2019-08-13T22:08:14 Z Bench0310 Split the Attractions (IOI19_split) C++14
40 / 100
 2000 ms 23084 KB 
#include <bits/stdc++.h>

using namespace std;

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

void solve_two(int num,int t)
{
    queue<int> q;
    q.push(centroid);
    while(num>0)
    {
        if(q.empty()) while(1);
        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);
    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);
        solve_two(abc[1].first,abc[1].second);
        solve_three(abc[2].second);
        return res;
    }
    return res;
}

/*int main()
{
    int _n,_m;
    scanf("%d%d",&_n,&_m);
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    vector<int> one,two;
    for(int i=0;i<_m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        one.push_back(x);
        two.push_back(y);
    }
    vector<int> temp=find_split(_n,a,b,c,one,two);
    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 9 ms 8184 KB ok, correct split
3 Correct 9 ms 8188 KB ok, correct split
4 Correct 9 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 Correct 157 ms 22776 KB ok, correct split
8 Correct 141 ms 20984 KB ok, correct split
9 Correct 140 ms 20448 KB ok, correct split
10 Correct 148 ms 23084 KB ok, correct split
11 Correct 156 ms 22992 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB ok, correct split
2 Correct 9 ms 8184 KB ok, correct split
3 Correct 9 ms 8200 KB ok, correct split
4 Correct 152 ms 21112 KB ok, correct split
5 Correct 120 ms 17016 KB ok, correct split
6 Correct 151 ms 23072 KB ok, correct split
7 Correct 126 ms 20728 KB ok, correct split
8 Correct 165 ms 18848 KB ok, correct split
9 Correct 161 ms 16892 KB ok, correct split
10 Correct 97 ms 18132 KB ok, correct split
11 Correct 99 ms 18004 KB ok, correct split
12 Correct 104 ms 18132 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB ok, correct split
2 Correct 120 ms 16988 KB ok, correct split
3 Correct 55 ms 11768 KB ok, correct split
4 Correct 9 ms 8184 KB ok, correct split
5 Correct 136 ms 18808 KB ok, correct split
6 Correct 146 ms 18792 KB ok, correct split
7 Correct 130 ms 18780 KB ok, correct split
8 Correct 140 ms 19652 KB ok, correct split
9 Correct 133 ms 18704 KB ok, correct split
10 Correct 39 ms 11128 KB ok, no valid answer
11 Correct 58 ms 12664 KB ok, no valid answer
12 Correct 119 ms 17780 KB ok, no valid answer
13 Correct 170 ms 17144 KB ok, no valid answer
14 Correct 145 ms 18160 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8196 KB ok, correct split
2 Correct 9 ms 8312 KB ok, no valid answer
3 Correct 9 ms 8184 KB ok, correct split
4 Correct 9 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 Correct 9 ms 8184 KB ok, correct split
8 Execution timed out 2058 ms 8184 KB Time limit exceeded
9 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 9 ms 8184 KB ok, correct split
3 Correct 9 ms 8188 KB ok, correct split
4 Correct 9 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 Correct 157 ms 22776 KB ok, correct split
8 Correct 141 ms 20984 KB ok, correct split
9 Correct 140 ms 20448 KB ok, correct split
10 Correct 148 ms 23084 KB ok, correct split
11 Correct 156 ms 22992 KB ok, correct split
12 Correct 9 ms 8184 KB ok, correct split
13 Correct 9 ms 8184 KB ok, correct split
14 Correct 9 ms 8200 KB ok, correct split
15 Correct 152 ms 21112 KB ok, correct split
16 Correct 120 ms 17016 KB ok, correct split
17 Correct 151 ms 23072 KB ok, correct split
18 Correct 126 ms 20728 KB ok, correct split
19 Correct 165 ms 18848 KB ok, correct split
20 Correct 161 ms 16892 KB ok, correct split
21 Correct 97 ms 18132 KB ok, correct split
22 Correct 99 ms 18004 KB ok, correct split
23 Correct 104 ms 18132 KB ok, correct split
24 Correct 9 ms 8184 KB ok, correct split
25 Correct 120 ms 16988 KB ok, correct split
26 Correct 55 ms 11768 KB ok, correct split
27 Correct 9 ms 8184 KB ok, correct split
28 Correct 136 ms 18808 KB ok, correct split
29 Correct 146 ms 18792 KB ok, correct split
30 Correct 130 ms 18780 KB ok, correct split
31 Correct 140 ms 19652 KB ok, correct split
32 Correct 133 ms 18704 KB ok, correct split
33 Correct 39 ms 11128 KB ok, no valid answer
34 Correct 58 ms 12664 KB ok, no valid answer
35 Correct 119 ms 17780 KB ok, no valid answer
36 Correct 170 ms 17144 KB ok, no valid answer
37 Correct 145 ms 18160 KB ok, no valid answer
38 Correct 9 ms 8196 KB ok, correct split
39 Correct 9 ms 8312 KB ok, no valid answer
40 Correct 9 ms 8184 KB ok, correct split
41 Correct 9 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 Correct 9 ms 8184 KB ok, correct split
45 Execution timed out 2058 ms 8184 KB Time limit exceeded
46 Halted 0 ms 0 KB -