oj.uz

Submission #825228

# Submission time Handle Problem Language Result Execution time Memory
825228 2023-08-14T15:55:31 Z ZHIRDILBILDIZ Split the Attractions (IOI19_split) C++14
18 / 100
 87 ms 25140 KB 
#include<bits/stdc++.h>
#include "split.h"
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = 1e5 ;
bool us[N + 1] ;
int vert, sz[N + 1], ind[N + 1] ;
vector<int> ts, res, v[N + 1], other[N + 1], tree[N + 1] ;
void ultra_clear()
{
    for(int i = 0 ; i < N ; i++)
        us[i] = 0 ;
}
void build_tree(int city)
{
    us[city] = 1 ;
    for(int i : v[city])
    {
        if(us[i])
            continue ;
        tree[city].push_back(i) ;
        build_tree(i) ;
    }
}
void dfs_for_tree(int city, int a1)
{
    ind[city] = ts.size() ;
    ts.push_back(city) ;
    sz[city]++ ;
    int mx = 0 ;
    for(int i : tree[city])
    {
        dfs_for_tree(i, a1) ;
        mx = max(mx, sz[i]) ;
        sz[city] += sz[i] ;
    }
    if(mx < a1 && sz[city] >= a1)
        vert = city ;
}
void dfs_color(int city, int &cnt, int color)
{
    us[city] = 1 ;
    if(cnt)
    {
        cnt-- ;
        res[city] = color ;
    }
    for(int i : tree[city])
    {
        if(us[i])
            continue ;
        dfs_color(i, cnt, color) ;
    }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> fr, vector<int> to)
{
    vector<pair<int, int>> all = {{a, 1}, {b, 2}, {c, 3}} ;
    sort(all.begin(), all.end()) ;
    int m = fr.size() ;
    for(int i = 0 ; i < n ; i++)
        res.push_back(0) ;
    for(int i = 0 ; i < m ; i++)
    {
        v[fr[i]].push_back(to[i]) ;
        v[to[i]].push_back(fr[i]) ;
    }
    build_tree(0) ;
    dfs_for_tree(0, all[0].fi) ;
    for(int i = 0 ; i < m ; i++)
    {
        int f = fr[i], t = to[i] ;
        if(ind[vert] <= ind[f] && ind[f] < ind[vert] + sz[vert] && ind[t] < ind[vert])
            other[f].push_back(t) ;
        if(ind[vert] <= ind[t] && ind[t] < ind[vert] + sz[vert] && ind[f] < ind[vert])
            other[t].push_back(f) ;
    }
    vector<int> del ;
    for(int i = ind[vert] + 1 ; i < ind[vert] + sz[vert] ; i++)
    {
        int now = ts[i] ;
        if(sz[vert] - sz[now] >= all[0].fi && other[now].size())
        {
            del.push_back(now) ;
            tree[other[now][0]].push_back(now) ;
            us[now] = 1 ;
            sz[vert] -= sz[now] ;
            i = ind[now] + sz[now] - 1 ;
        }
    }
    if(sz[vert] >= all[0].fi && n - sz[vert] >= all[1].fi)
    {
        ultra_clear() ;
        dfs_color(vert, all[0].fi, all[0].se) ;
        for(int i : del)
            us[i] = 0 ;
        dfs_color(0, all[1].fi, all[1].se) ;
        for(int i = 0 ; i < n ; i++)
            if(!res[i])
                res[i] = all[2].se ;
    }
    return res ;
}
//signed main()
//{
//    ios_base::sync_with_stdio( 0 ) ;
//    cin.tie( 0 ) ;
//    cout.tie( 0 ) ;
//    int n, m, a, b, c ;
//    cin >> n >> a >> b >> c >> m ;
//    vector<int> fr(m), to(m) ;
//    for(int i = 0 ; i < m ; i++)
//        cin >> fr[i] >> to[i] ;
//    vector<int> ans = find_split(n, a, b, c, fr, to) ;
//    for(int i : ans)
//        cout << i << ' ' ;
//    return 0 ;
//}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB ok, correct split
2 Correct 3 ms 7380 KB ok, correct split
3 Correct 3 ms 7380 KB ok, correct split
4 Correct 3 ms 7440 KB ok, correct split
5 Correct 3 ms 7380 KB ok, correct split
6 Correct 3 ms 7380 KB ok, correct split
7 Correct 79 ms 24668 KB ok, correct split
8 Correct 66 ms 22468 KB ok, correct split
9 Correct 67 ms 21848 KB ok, correct split
10 Correct 63 ms 25108 KB ok, correct split
11 Correct 68 ms 25140 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB ok, correct split
2 Correct 3 ms 7380 KB ok, correct split
3 Correct 4 ms 7380 KB ok, correct split
4 Correct 84 ms 20932 KB ok, correct split
5 Correct 59 ms 15940 KB ok, correct split
6 Correct 65 ms 25116 KB ok, correct split
7 Correct 69 ms 22260 KB ok, correct split
8 Correct 87 ms 18588 KB ok, correct split
9 Correct 55 ms 17316 KB ok, correct split
10 Correct 41 ms 14948 KB ok, correct split
11 Correct 41 ms 14908 KB ok, correct split
12 Correct 51 ms 14916 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB ok, correct split
2 Incorrect 57 ms 15948 KB jury found a solution, contestant did not
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB ok, correct split
2 Correct 3 ms 7252 KB ok, no valid answer
3 Correct 4 ms 7380 KB ok, correct split
4 Correct 3 ms 7380 KB ok, correct split
5 Correct 3 ms 7380 KB ok, correct split
6 Correct 4 ms 7380 KB ok, correct split
7 Correct 3 ms 7380 KB ok, correct split
8 Correct 3 ms 7380 KB ok, correct split
9 Correct 5 ms 7764 KB ok, correct split
10 Correct 5 ms 7636 KB ok, correct split
11 Correct 3 ms 7380 KB ok, correct split
12 Correct 6 ms 7764 KB ok, correct split
13 Correct 4 ms 7380 KB ok, correct split
14 Correct 3 ms 7380 KB ok, correct split
15 Correct 3 ms 7380 KB ok, correct split
16 Correct 3 ms 7380 KB ok, correct split
17 Incorrect 3 ms 7380 KB invalid split: #1=15, #2=17, #3=6
18 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB ok, correct split
2 Correct 3 ms 7380 KB ok, correct split
3 Correct 3 ms 7380 KB ok, correct split
4 Correct 3 ms 7440 KB ok, correct split
5 Correct 3 ms 7380 KB ok, correct split
6 Correct 3 ms 7380 KB ok, correct split
7 Correct 79 ms 24668 KB ok, correct split
8 Correct 66 ms 22468 KB ok, correct split
9 Correct 67 ms 21848 KB ok, correct split
10 Correct 63 ms 25108 KB ok, correct split
11 Correct 68 ms 25140 KB ok, correct split
12 Correct 3 ms 7380 KB ok, correct split
13 Correct 3 ms 7380 KB ok, correct split
14 Correct 4 ms 7380 KB ok, correct split
15 Correct 84 ms 20932 KB ok, correct split
16 Correct 59 ms 15940 KB ok, correct split
17 Correct 65 ms 25116 KB ok, correct split
18 Correct 69 ms 22260 KB ok, correct split
19 Correct 87 ms 18588 KB ok, correct split
20 Correct 55 ms 17316 KB ok, correct split
21 Correct 41 ms 14948 KB ok, correct split
22 Correct 41 ms 14908 KB ok, correct split
23 Correct 51 ms 14916 KB ok, correct split
24 Correct 3 ms 7380 KB ok, correct split
25 Incorrect 57 ms 15948 KB jury found a solution, contestant did not
26 Halted 0 ms 0 KB -