oj.uz

Submission #143382

# Submission time Handle Problem Language Result Execution time Memory
143382 2019-08-13T22:03:51 Z Bench0310 Split the Attractions (IOI19_split) C++14
40 / 100
 164 ms 23032 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)
    {
        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 10 ms 8184 KB ok, correct split
2 Correct 10 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 10 ms 8184 KB ok, correct split
6 Correct 10 ms 8184 KB ok, correct split
7 Correct 153 ms 22776 KB ok, correct split
8 Correct 139 ms 21112 KB ok, correct split
9 Correct 141 ms 20416 KB ok, correct split
10 Correct 148 ms 23032 KB ok, correct split
11 Correct 161 ms 23004 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 8 ms 8184 KB ok, correct split
3 Correct 8 ms 8184 KB ok, correct split
4 Correct 154 ms 21064 KB ok, correct split
5 Correct 141 ms 17096 KB ok, correct split
6 Correct 142 ms 23032 KB ok, correct split
7 Correct 138 ms 20856 KB ok, correct split
8 Correct 160 ms 18808 KB ok, correct split
9 Correct 125 ms 16860 KB ok, correct split
10 Correct 95 ms 18104 KB ok, correct split
11 Correct 95 ms 18132 KB ok, correct split
12 Correct 94 ms 18164 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 123 ms 17100 KB ok, correct split
3 Correct 46 ms 11900 KB ok, correct split
4 Correct 9 ms 8184 KB ok, correct split
5 Correct 134 ms 18936 KB ok, correct split
6 Correct 138 ms 18680 KB ok, correct split
7 Correct 164 ms 18760 KB ok, correct split
8 Correct 142 ms 19576 KB ok, correct split
9 Correct 150 ms 18680 KB ok, correct split
10 Correct 42 ms 11256 KB ok, no valid answer
11 Correct 60 ms 12536 KB ok, no valid answer
12 Correct 117 ms 17780 KB ok, no valid answer
13 Correct 131 ms 17236 KB ok, no valid answer
14 Correct 119 ms 18036 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 10 ms 8184 KB ok, no valid answer
3 Correct 9 ms 8184 KB ok, correct split
4 Correct 8 ms 8184 KB ok, correct split
5 Correct 9 ms 8156 KB ok, correct split
6 Correct 9 ms 8188 KB ok, correct split
7 Correct 9 ms 8184 KB ok, correct split
8 Runtime error 19 ms 16376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8184 KB ok, correct split
2 Correct 10 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 10 ms 8184 KB ok, correct split
6 Correct 10 ms 8184 KB ok, correct split
7 Correct 153 ms 22776 KB ok, correct split
8 Correct 139 ms 21112 KB ok, correct split
9 Correct 141 ms 20416 KB ok, correct split
10 Correct 148 ms 23032 KB ok, correct split
11 Correct 161 ms 23004 KB ok, correct split
12 Correct 9 ms 8184 KB ok, correct split
13 Correct 8 ms 8184 KB ok, correct split
14 Correct 8 ms 8184 KB ok, correct split
15 Correct 154 ms 21064 KB ok, correct split
16 Correct 141 ms 17096 KB ok, correct split
17 Correct 142 ms 23032 KB ok, correct split
18 Correct 138 ms 20856 KB ok, correct split
19 Correct 160 ms 18808 KB ok, correct split
20 Correct 125 ms 16860 KB ok, correct split
21 Correct 95 ms 18104 KB ok, correct split
22 Correct 95 ms 18132 KB ok, correct split
23 Correct 94 ms 18164 KB ok, correct split
24 Correct 9 ms 8184 KB ok, correct split
25 Correct 123 ms 17100 KB ok, correct split
26 Correct 46 ms 11900 KB ok, correct split
27 Correct 9 ms 8184 KB ok, correct split
28 Correct 134 ms 18936 KB ok, correct split
29 Correct 138 ms 18680 KB ok, correct split
30 Correct 164 ms 18760 KB ok, correct split
31 Correct 142 ms 19576 KB ok, correct split
32 Correct 150 ms 18680 KB ok, correct split
33 Correct 42 ms 11256 KB ok, no valid answer
34 Correct 60 ms 12536 KB ok, no valid answer
35 Correct 117 ms 17780 KB ok, no valid answer
36 Correct 131 ms 17236 KB ok, no valid answer
37 Correct 119 ms 18036 KB ok, no valid answer
38 Correct 8 ms 8184 KB ok, correct split
39 Correct 10 ms 8184 KB ok, no valid answer
40 Correct 9 ms 8184 KB ok, correct split
41 Correct 8 ms 8184 KB ok, correct split
42 Correct 9 ms 8156 KB ok, correct split
43 Correct 9 ms 8188 KB ok, correct split
44 Correct 9 ms 8184 KB ok, correct split
45 Runtime error 19 ms 16376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
46 Halted 0 ms 0 KB -