oj.uz

Submission #923936

# Submission time Handle Problem Language Result Execution time Memory
923936 2024-02-08T06:46:33 Z boris_mihov Mergers (JOI19_mergers) C++17
0 / 100
 68 ms 29616 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <bitset>
#include <random>
#include <queue>
#include <set>
 
typedef long long llong;
const int MAXN = 500000 + 10;
const int INTINF = 2e9;
const llong INF = 1e18;
const int MAXLOG = 17;
 
int n, k;
int s[MAXN];
int sz[MAXN];
int cnt[MAXN];
int full[MAXN];
int szBad[MAXN];
int szLeaf[MAXN];
bool isBad[MAXN];
std::vector <int> g[MAXN];
 
void buildDFS(int node, int par)
{
    for (int &u : g[node])
    {
        if (u == par)
        {
            std::swap(u, g[node].back());
            g[node].pop_back();
            break;
        }
    }
 
    sz[node] = 1;
    for (const int &u : g[node])
    {
        buildDFS(u, node);
        sz[node] += sz[u];
    }
 
    for (int i = 1 ; i < g[node].size() ; ++i)
    {
        if (sz[g[node][i]] > sz[g[node][0]])
        {
            std::swap(g[node][i], g[node][0]);
        }
    }
}
 
int cntUnfull;
void addNode(int node)
{
    cntUnfull -= (0 < cnt[s[node]] && cnt[s[node]] < full[s[node]]);
    cnt[s[node]]++;
    cntUnfull += (0 < cnt[s[node]] && cnt[s[node]] < full[s[node]]);
}
 
void remNode(int node)
{
    cntUnfull -= (0 < cnt[s[node]] && cnt[s[node]] < full[s[node]]);
    cnt[s[node]]--;
    cntUnfull += (0 < cnt[s[node]] && cnt[s[node]] < full[s[node]]);
}
 
void addDFS(int node)
{
    addNode(node);
    for (const int &u : g[node])
    {
        addDFS(u);
    }
}
 
void remDFS(int node)
{
    remNode(node);
    for (const int &u : g[node])
    {
        remDFS(u);
    }
}
 
void solveDFS(int node)
{
    for (int i = 1 ; i < g[node].size() ; ++i)
    {
        solveDFS(g[node][i]);
        remDFS(g[node][i]);
    }
 
    if (g[node].size())
    {
        solveDFS(g[node][0]);
    }
 
    for (int i = 1 ; i < g[node].size() ; ++i)
    {
        addDFS(g[node][i]);
    }
 
    addNode(node);
    if (cntUnfull == 0)
    {
        isBad[node] = true;
    }
}
 
int leaveCnt;
int coverCnt;
void calcDFS(int node)
{
    szBad[node] = isBad[node];
    for (const int &u : g[node])
    {
        calcDFS(u);
        szBad[node] += szBad[u];
    }
}
 
void ansDFS(int node)
{
    szLeaf[node] = isBad[node] && (szBad[node] == 1);
    for (const int &u : g[node])
    {
        ansDFS(u);
        szLeaf[node] += szLeaf[u];
    }
}
 
void solve()
{
    buildDFS(1, 0);
    solveDFS(1);
    isBad[1] = false;
    calcDFS(1);
    ansDFS(1);
    
    for (int i = 2 ; i <= n ; ++i)
    {
        if (isBad[i])
        {
            coverCnt += (szLeaf[i] > 1 && szLeaf[i] == szLeaf[1]);
            leaveCnt += (szBad[i] == 1);
        }
    }   
 
    coverCnt = (coverCnt > 0);
    std::cout << leaveCnt / 2 + (leaveCnt % 2) + coverCnt << '\n';
}
 
void input()
{
    std::cin >> n >> k;
    for (int i = 1 ; i < n ; ++i)
    {
        int u, v;
        std::cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
 
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> s[i];
        full[s[i]]++;
    }
}
 
void fastIOI()
{   
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}
 
int main()
{
    fastIOI();
    input();
    solve();
 
    return 0;
}

Compilation message

mergers.cpp: In function 'void buildDFS(int, int)':
mergers.cpp:46:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 1 ; i < g[node].size() ; ++i)
      |                      ~~^~~~~~~~~~~~~~~~
mergers.cpp: In function 'void solveDFS(int)':
mergers.cpp:90:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for (int i = 1 ; i < g[node].size() ; ++i)
      |                      ~~^~~~~~~~~~~~~~~~
mergers.cpp:101:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for (int i = 1 ; i < g[node].size() ; ++i)
      |                      ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 4 ms 21080 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 4 ms 21152 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 4 ms 21096 KB Output is correct
8 Correct 4 ms 21084 KB Output is correct
9 Correct 4 ms 21096 KB Output is correct
10 Correct 4 ms 21080 KB Output is correct
11 Correct 4 ms 21084 KB Output is correct
12 Incorrect 4 ms 21084 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 4 ms 21080 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 4 ms 21152 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 4 ms 21096 KB Output is correct
8 Correct 4 ms 21084 KB Output is correct
9 Correct 4 ms 21096 KB Output is correct
10 Correct 4 ms 21080 KB Output is correct
11 Correct 4 ms 21084 KB Output is correct
12 Incorrect 4 ms 21084 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 4 ms 21080 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 4 ms 21152 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 4 ms 21096 KB Output is correct
8 Correct 4 ms 21084 KB Output is correct
9 Correct 4 ms 21096 KB Output is correct
10 Correct 4 ms 21080 KB Output is correct
11 Correct 4 ms 21084 KB Output is correct
12 Incorrect 4 ms 21084 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24428 KB Output is correct
2 Correct 35 ms 24944 KB Output is correct
3 Correct 5 ms 21084 KB Output is correct
4 Correct 5 ms 21084 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 4 ms 21148 KB Output is correct
7 Correct 6 ms 21084 KB Output is correct
8 Correct 64 ms 26196 KB Output is correct
9 Correct 6 ms 21260 KB Output is correct
10 Correct 53 ms 25700 KB Output is correct
11 Correct 4 ms 21084 KB Output is correct
12 Correct 55 ms 25684 KB Output is correct
13 Correct 62 ms 26192 KB Output is correct
14 Correct 58 ms 26288 KB Output is correct
15 Correct 31 ms 25932 KB Output is correct
16 Correct 5 ms 21256 KB Output is correct
17 Correct 4 ms 21084 KB Output is correct
18 Correct 53 ms 26732 KB Output is correct
19 Correct 68 ms 29616 KB Output is correct
20 Correct 5 ms 21336 KB Output is correct
21 Incorrect 4 ms 21080 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 4 ms 21080 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 4 ms 21152 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 4 ms 21096 KB Output is correct
8 Correct 4 ms 21084 KB Output is correct
9 Correct 4 ms 21096 KB Output is correct
10 Correct 4 ms 21080 KB Output is correct
11 Correct 4 ms 21084 KB Output is correct
12 Incorrect 4 ms 21084 KB Output isn't correct
13 Halted 0 ms 0 KB -