oj.uz

Submission #825219

# Submission time Handle Problem Language Result Execution time Memory
825219 2023-08-14T15:47:38 Z ZHIRDILBILDIZ Split the Attractions (IOI19_split) C++14
18 / 100
 77 ms 25128 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 = 1 ; 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 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 71 ms 24792 KB ok, correct split
8 Correct 74 ms 22528 KB ok, correct split
9 Correct 57 ms 21720 KB ok, correct split
10 Correct 64 ms 25112 KB ok, correct split
11 Correct 62 ms 25088 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7376 KB ok, correct split
2 Correct 3 ms 7380 KB ok, correct split
3 Correct 3 ms 7380 KB ok, correct split
4 Correct 70 ms 20912 KB ok, correct split
5 Correct 61 ms 15940 KB ok, correct split
6 Correct 64 ms 25128 KB ok, correct split
7 Correct 62 ms 22216 KB ok, correct split
8 Correct 77 ms 18520 KB ok, correct split
9 Correct 54 ms 17348 KB ok, correct split
10 Correct 42 ms 14920 KB ok, correct split
11 Correct 41 ms 14932 KB ok, correct split
12 Correct 42 ms 15004 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB ok, correct split
2 Incorrect 51 ms 15932 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 3 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 3 ms 7380 KB ok, correct split
7 Correct 4 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 5 ms 7764 KB ok, correct split
13 Correct 3 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 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 71 ms 24792 KB ok, correct split
8 Correct 74 ms 22528 KB ok, correct split
9 Correct 57 ms 21720 KB ok, correct split
10 Correct 64 ms 25112 KB ok, correct split
11 Correct 62 ms 25088 KB ok, correct split
12 Correct 4 ms 7376 KB ok, correct split
13 Correct 3 ms 7380 KB ok, correct split
14 Correct 3 ms 7380 KB ok, correct split
15 Correct 70 ms 20912 KB ok, correct split
16 Correct 61 ms 15940 KB ok, correct split
17 Correct 64 ms 25128 KB ok, correct split
18 Correct 62 ms 22216 KB ok, correct split
19 Correct 77 ms 18520 KB ok, correct split
20 Correct 54 ms 17348 KB ok, correct split
21 Correct 42 ms 14920 KB ok, correct split
22 Correct 41 ms 14932 KB ok, correct split
23 Correct 42 ms 15004 KB ok, correct split
24 Correct 4 ms 7380 KB ok, correct split
25 Incorrect 51 ms 15932 KB jury found a solution, contestant did not
26 Halted 0 ms 0 KB -