Submission #979323

#	Time	Username	Problem	Language	Result	Execution time	Memory
979323		Requiem	Railway (BOI17_railway)	C++17	100 / 100	134 ms	127176 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];

int tmpPar[MAXN];


namespace subtask1{
    bool checkSubtask1(){
        int S = 0;
        for(int i = 1; i <= m; i++){
            S += Q[i].num;
        }
        return S <= 2000 and n <= 10000;
    }

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

    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];
         }
    }

    int root(int u){
        if (u == tmpPar[u]) return u;
        else return tmpPar[u] = root(tmpPar[u]);
    }
    void go(int u, int v){
         while(u != v){
            u = root(u);
            v = root(v);
            if (u == v) break;
            if (depth[u] < depth[v]) swap(u, v);

            FreqCount[par[u].se]++;
            tmpPar[u] = par[u].fi;
         }
    }
    void solveSubtask1(){
         dfs(1, -1);

         for(int i = 1; i <= m; i++){
             int num = Q[i].num;
             iota(tmpPar + 1, tmpPar + 1 + n, 1);

             for(int j = 0; j < num; j++){
                 for(int k = j + 1; k < num; k++){
                     go(Q[i].QueryVert[j], Q[i].QueryVert[k]);
                 }
             }
         }
         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;

    }
}

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());

//
//         for(int i = 0; i < Vertice.size(); i++){
//             cout << Vertice[i] << ' ';
//         }
//         cout << endl;
         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();
                 }

//                 cout << curStack.back() << ' ' << Vertice[i] << endl;
                 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(){
        dfs(1, -1);
//        for(int i = 0; i < etour.size(); i++){
//            cout << etour[i] << ' ';
//        }
//        cout << endl;
//
//        for(int i = 1; i <= n; i++){
//            cout << in[i] << ' ' << out[i] << endl;
//        }

        //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++){
//            cout << FreqCount[i] << ' ';
            if (FreqCount[i] >= k) ans.pb(i);
        }
//        cout << endl;

        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 (subtask1::checkSubtask1()) return subtask1::solveSubtask1(), 0;
    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:175: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]
  175 |          for(int i = 0; i < Vertice.size(); i++){
      |                         ~~^~~~~~~~~~~~~~~~
railway.cpp:178:22: warning: unused variable 'x' [-Wunused-variable]
  178 |                  int x = curStack.back();
      |                      ^
railway.cpp: In function 'void subtask2::solveSubtask2()':
railway.cpp:214: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]
  214 |         for(int i = 1; i < etour.size(); i++){
      |                        ~~^~~~~~~~~~~~~~
railway.cpp:219: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]
  219 |             for(int j = 1; j + (1 << i) - 1 < etour.size(); j++){
      |                            ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
railway.cpp: At global scope:
railway.cpp:247:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  247 | main()
      | ^~~~
railway.cpp: In function 'int main()':
railway.cpp:251:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  251 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:252:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  252 |         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