oj.uz

Submission #957471

# Submission time Handle Problem Language Result Execution time Memory
957471 2024-04-03T20:37:21 Z n3rm1n Railway (BOI17_railway) C++17
23 / 100
 307 ms 524288 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 2e5 + 10, MAXLOG = 23;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n, m, k;
vector < pair < int, int > > g[MAXN];
void read_graph()
{
    cin >> n >> m >> k;
    int from, to;
    for (int i = 1; i < n; ++ i)
    {
        cin >> from >> to;
        g[from].push_back({to, i});
        g[to].push_back({from, i});
    }
}

int p[MAXN], lvl[MAXN];
void dfs(int beg, int par, int depth)
{
    p[beg] = par;
    lvl[beg] = depth;
    int nb;
    for (int i = 0; i < g[beg].size(); ++ i)
    {
        nb = g[beg][i].first;
        if(lvl[nb] == 0)dfs(nb, beg, depth+1);
    }
}
int jump[MAXN][MAXLOG];
void fill_jump()
{
    for (int i = 1; i <= n; ++ i)
        jump[i][0] = p[i];
    for (int j = 1; j < MAXLOG; ++ j)
        for (int i = 1; i <= n; ++ i)
            jump[i][j] = jump[jump[i][j-1]][j-1];
}
int move_up(int v, int dist)
{
    for (int i = 0; (1 << i) <= dist; ++ i)
    {
        if((1 << i) & dist)
            v = jump[v][i];
    }
    return v;
}
int lca(int u, int v)
{
    int stu = u;
    int stv = v;
    if(lvl[u] > lvl[v])swap(u, v);
    int diff = lvl[v] - lvl[u];
    v = move_up(v, diff);
    //cout << "! " << stu << " " << stv << " "<< diff << endl;
    //cout << "newv " << v << endl;
    if(u == v)return u;
    int to = u;

    for (int i = MAXLOG - 1; i >= 0; -- i)
    {
        if(jump[u][i] != jump[v][i])
        {
            u = jump[u][i];
            v = jump[v][i];
        }
    }
    //cout << "for " << stu << ", " << stv << " is " << p[u] << endl;
    return p[u];
}
int s;
vector < int > que[MAXN];
vector < int /*colours*/ > endpoints[MAXN], startpoints[MAXN];
int cnt[MAXN];
int used[MAXN], active[MAXN];
int ans[MAXN];
bitset < MAXN > dfs2(int beg)
{
    used[beg] = 1;
    /// add

    int nb, id;
    bitset < MAXN > bs, vs;
    for (int i = 0; i < g[beg].size(); ++ i)
    {
        nb = g[beg][i].first;
        id = g[beg][i].second;

        if(!used[nb])
        {
            vs = dfs2(nb);
            bs = (bs | vs);
            ans[id] += vs.count();
        }
    }
    for (int i = 0; i < endpoints[beg].size(); ++ i)
    {
        bs[endpoints[beg][i]] = 1;
    }
    for (int i = 0; i < startpoints[beg].size(); ++ i)
    {
        bs[startpoints[beg][i]] = 0;
    }
    return bs;
}
void read_queries()
{
    int xx;
    for (int i = 1; i <= m; ++ i)
    {
        cin >> s >> xx;
        int lcaa = xx;
        que[i].push_back(xx);
        for (int j = 2; j <= s; ++ j)
        {
            cin >> xx;
            que[i].push_back(xx);
            lcaa = lca(lcaa, xx);
        }
        startpoints[lcaa].push_back(i);
       // cout << i << " lca is " << lcaa << endl;
        for (int j = 0; j < que[i].size(); ++ j)
        {

            endpoints[que[i][j]].push_back(i);
        }
    }

}
int main()
{
    speed();

    read_graph();
    dfs(1, 0, 1);
    fill_jump();
    read_queries();
    dfs2(1);


    vector < int > anss;
    for (int i = 1; i <= n; ++ i)
    {
        if(ans[i] >= k)anss.push_back(i);
    }

    cout << anss.size() << endl;
    for (int i = 0; i < anss.size(); ++ i)
        cout << anss[i] << " ";
    cout << endl;
    return 0;
}

Compilation message

railway.cpp: In function 'void dfs(int, int, int)':
railway.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i = 0; i < g[beg].size(); ++ i)
      |                     ~~^~~~~~~~~~~~~~~
railway.cpp: In function 'int lca(int, int)':
railway.cpp:57:9: warning: unused variable 'stu' [-Wunused-variable]
   57 |     int stu = u;
      |         ^~~
railway.cpp:58:9: warning: unused variable 'stv' [-Wunused-variable]
   58 |     int stv = v;
      |         ^~~
railway.cpp:65:9: warning: unused variable 'to' [-Wunused-variable]
   65 |     int to = u;
      |         ^~
railway.cpp: In function 'std::bitset<200010> dfs2(int)':
railway.cpp:91:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for (int i = 0; i < g[beg].size(); ++ i)
      |                     ~~^~~~~~~~~~~~~~~
railway.cpp:103:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for (int i = 0; i < endpoints[beg].size(); ++ i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:107:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for (int i = 0; i < startpoints[beg].size(); ++ i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp: In function 'void read_queries()':
railway.cpp:129:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         for (int j = 0; j < que[i].size(); ++ j)
      |                         ~~^~~~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:155:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     for (int i = 0; i < anss.size(); ++ i)
      |                     ~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25436 KB Output is correct
2 Correct 102 ms 26788 KB Output is correct
3 Correct 110 ms 26960 KB Output is correct
4 Correct 6 ms 26204 KB Output is correct
5 Correct 6 ms 26204 KB Output is correct
6 Correct 240 ms 271168 KB Output is correct
7 Correct 130 ms 75048 KB Output is correct
8 Correct 103 ms 26268 KB Output is correct
9 Correct 103 ms 26460 KB Output is correct
10 Correct 6 ms 25688 KB Output is correct
11 Correct 6 ms 25688 KB Output is correct
12 Correct 6 ms 25688 KB Output is correct
13 Correct 5 ms 25948 KB Output is correct
14 Correct 6 ms 25948 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25436 KB Output is correct
2 Correct 102 ms 26788 KB Output is correct
3 Correct 110 ms 26960 KB Output is correct
4 Correct 6 ms 26204 KB Output is correct
5 Correct 6 ms 26204 KB Output is correct
6 Correct 240 ms 271168 KB Output is correct
7 Correct 130 ms 75048 KB Output is correct
8 Correct 103 ms 26268 KB Output is correct
9 Correct 103 ms 26460 KB Output is correct
10 Correct 6 ms 25688 KB Output is correct
11 Correct 6 ms 25688 KB Output is correct
12 Correct 6 ms 25688 KB Output is correct
13 Correct 5 ms 25948 KB Output is correct
14 Correct 6 ms 25948 KB Output is correct
15 Correct 112 ms 28652 KB Output is correct
16 Correct 122 ms 28268 KB Output is correct
17 Correct 113 ms 28440 KB Output is correct
18 Correct 231 ms 271196 KB Output is correct
19 Correct 131 ms 75124 KB Output is correct
20 Correct 117 ms 27736 KB Output is correct
21 Correct 112 ms 27736 KB Output is correct
22 Correct 5 ms 25436 KB Output is correct
23 Correct 118 ms 26972 KB Output is correct
24 Correct 105 ms 26716 KB Output is correct
25 Correct 6 ms 26204 KB Output is correct
26 Correct 6 ms 26204 KB Output is correct
27 Correct 235 ms 271028 KB Output is correct
28 Correct 159 ms 75184 KB Output is correct
29 Correct 107 ms 26216 KB Output is correct
30 Correct 101 ms 26568 KB Output is correct
31 Correct 6 ms 25688 KB Output is correct
32 Correct 6 ms 25944 KB Output is correct
33 Correct 5 ms 25944 KB Output is correct
34 Correct 6 ms 25692 KB Output is correct
35 Correct 8 ms 25948 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 307 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 284 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 284 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25436 KB Output is correct
2 Correct 102 ms 26788 KB Output is correct
3 Correct 110 ms 26960 KB Output is correct
4 Correct 6 ms 26204 KB Output is correct
5 Correct 6 ms 26204 KB Output is correct
6 Correct 240 ms 271168 KB Output is correct
7 Correct 130 ms 75048 KB Output is correct
8 Correct 103 ms 26268 KB Output is correct
9 Correct 103 ms 26460 KB Output is correct
10 Correct 6 ms 25688 KB Output is correct
11 Correct 6 ms 25688 KB Output is correct
12 Correct 6 ms 25688 KB Output is correct
13 Correct 5 ms 25948 KB Output is correct
14 Correct 6 ms 25948 KB Output is correct
15 Correct 112 ms 28652 KB Output is correct
16 Correct 122 ms 28268 KB Output is correct
17 Correct 113 ms 28440 KB Output is correct
18 Correct 231 ms 271196 KB Output is correct
19 Correct 131 ms 75124 KB Output is correct
20 Correct 117 ms 27736 KB Output is correct
21 Correct 112 ms 27736 KB Output is correct
22 Correct 5 ms 25436 KB Output is correct
23 Correct 118 ms 26972 KB Output is correct
24 Correct 105 ms 26716 KB Output is correct
25 Correct 6 ms 26204 KB Output is correct
26 Correct 6 ms 26204 KB Output is correct
27 Correct 235 ms 271028 KB Output is correct
28 Correct 159 ms 75184 KB Output is correct
29 Correct 107 ms 26216 KB Output is correct
30 Correct 101 ms 26568 KB Output is correct
31 Correct 6 ms 25688 KB Output is correct
32 Correct 6 ms 25944 KB Output is correct
33 Correct 5 ms 25944 KB Output is correct
34 Correct 6 ms 25692 KB Output is correct
35 Correct 8 ms 25948 KB Output is correct
36 Runtime error 307 ms 524288 KB Execution killed with signal 9
37 Halted 0 ms 0 KB -