Submission #979324

#	Time	Username	Problem	Language	Result	Execution time	Memory
979324		Requiem	Railway (BOI17_railway)	C++17	100 / 100	117 ms	124872 KiB

railway

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "railway"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;

const int MAXN = 3e5 + 9;

vector<int> g[MAXN];

struct Query{
    int num;
    vector<int> QueryVert;
} Q[MAXN];

int n, m, k, S;
ii edge[MAXN], par[MAXN];
int QueryVert[MAXN], depth[MAXN], pre[MAXN], FreqCount[MAXN];


namespace subtask2{

    bool checkSubtask2(){
        return true;
    }

    vector<int> etour = {0};
    vector<int> virtualTree[MAXN];
    int in[MAXN], out[MAXN], FreqCount[MAXN], dfsTime = 0;
    ii P[MAXN * 2][21];

    void dfs(int u, int p){
         etour.pb(u);

         in[u] = ++dfsTime;
         for(auto id: g[u]){
             int v = edge[id].se + edge[id].fi - u;
             if (v == p) continue;
             depth[v] = depth[u] + 1;
             par[v] = {u, id};
             dfs(v, u);
             etour.pb(u);
             dfsTime++;
         }
         out[u] = dfsTime;
    }

    ii getrange(int l, int r){
       int x = log2(r - l + 1);
       return min(P[l][x], P[r - (1 << x) + 1][x]);
    }
    ii lca(int u, int v){
       return getrange(min(in[u], in[v]), max(in[u], in[v]));
    }

    bool inTree(int u, int v){  //Check if vertice v lie in the subtree of the vertice u
         return in[v] >= in[u] and in[v] <= out[u];
    }

    void VirtualTree(int num, vector<int> &Vertice){
         sort(Vertice.begin(), Vertice.end(), [&](const int &u, const int &v){
              return in[u] < in[v];
         });

         for(int i = 0; i < num - 1; i++){
             int u = Vertice[i];
             int v = Vertice[i + 1];
             ii acs = lca(u, v);

             Vertice.pb(acs.se);
         }


         sort(Vertice.begin(), Vertice.end(), [&](const int &u, const int &v){
              return in[u] < in[v];
         });

         Vertice.erase(unique(Vertice.begin(), Vertice.end()), Vertice.end());

         vector<int> curStack;
         for(int i = 0; i < Vertice.size(); i++){
             if (curStack.size() == 0) curStack.pb(Vertice[i]);
             else{
                 int x = curStack.back();

                 while(curStack.size() > 0 and !inTree(curStack.back(), Vertice[i])) {
                     curStack.pop_back();
                 }

                 pre[curStack.back()]--;
                 pre[Vertice[i]]++;
                 curStack.pb(Vertice[i]);

             }
         }
    }

    void CountAnswer(int u, int p){
         for(auto id: g[u]){
             int v = edge[id].se + edge[id].fi - u;
             if (v == p) continue;
             CountAnswer(v, u);
             FreqCount[id] += pre[v];
             pre[u] += pre[v];
         }
    }
    void solveSubtask2(){
        //preDfs
        dfs(1, -1);

        //Sparse Table For LCA
        for(int i = 1; i < etour.size(); i++){
            P[i][0] = ii(depth[etour[i]], etour[i]);
        }

        for(int i = 1; i <= 18; i++){
            for(int j = 1; j + (1 << i) - 1 < etour.size(); j++){
                P[j][i] = min(P[j][i - 1], P[j + (1 << (i - 1))][i - 1]);
            }
        }

        //Handle Queries
        for(int i = 1; i <= m; i++){
            int num = Q[i].num;
            VirtualTree(num, Q[i].QueryVert);  //Using Virtual Tree to handle Queries.
        }

        CountAnswer(1, -1);
        vector<int> ans;
        for(int i = 1; i < n; i++){
            if (FreqCount[i] >= k) ans.pb(i);
        }

        cout << ans.size() << endl;
        for(auto x: ans){
            cout << x << ' ';
        }
        cout << endl;

    }
}

main()
{
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }

    cin >> n >> m >> k;
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        g[u].pb(i);
        g[v].pb(i);
        edge[i] = {u, v};
    }

    for(int i = 1; i <= m; i++){
        cin >> Q[i].num;
        for(int j = 0; j < Q[i].num; j++){
            int x;
            cin >> x;
            Q[i].QueryVert.pb(x);
        }
    }

    if (subtask2::checkSubtask2()) return subtask2::solveSubtask2(), 0;
}
/**
Warning:
- MLE / TLE?
- Gioi han mang?
- Gia tri max phai luon gan cho -INF
- long long co can thiet khong?
- tran mang.
- code can than hon
- Nho sinh test de tranh RTE / TLE

--> Coi lai truoc khi nop
**/

Compilation message (stderr)

railway.cpp: In function 'void subtask2::VirtualTree(long long int, std::vector<long long int>&)':
railway.cpp:96:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |          for(int i = 0; i < Vertice.size(); i++){
      |                         ~~^~~~~~~~~~~~~~~~
railway.cpp:99:22: warning: unused variable 'x' [-Wunused-variable]
   99 |                  int x = curStack.back();
      |                      ^
railway.cpp: In function 'void subtask2::solveSubtask2()':
railway.cpp:127:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         for(int i = 1; i < etour.size(); i++){
      |                        ~~^~~~~~~~~~~~~~
railway.cpp:132:45: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |             for(int j = 1; j + (1 << i) - 1 < etour.size(); j++){
      |                            ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
railway.cpp: At global scope:
railway.cpp:158:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  158 | main()
      | ^~~~
railway.cpp: In function 'int main()':
railway.cpp:162:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:163:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25