Submission #344327

#	Time	Username	Problem	Language	Result	Execution time	Memory
344327		Atill83	Railway (BOI17_railway)	C++14	100 / 100	187 ms	29040 KiB

railway

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n, m, k;
vector<int> mns[MAXN];
vector<pii> adj[MAXN];
int up[MAXN], down[MAXN], sz[MAXN];
int cur = 0;
vector<int> ans;

void dfs(int v, int par){
    sz[v] = 1;

    for(int i = 0; i < adj[v].size(); i++){
        if(adj[v][i].ff == par){
            swap(adj[v][i], adj[v].back());
            adj[v].pop_back();
            break;
        }
    }

    for(pii j: adj[v]){
        dfs(j.ff, v);
        sz[v] += sz[j.ff];
    }

    for(int i = 1; i < adj[v].size(); i++){
        if(sz[adj[v][i].ff] > sz[adj[v][0].ff])
            swap(adj[v][i], adj[v][0]);
    }

}

void add(int v){
    for(int j: mns[v]){
        if(up[j] == 0)
            cur++;
        up[j]++;
        down[j]--;
        if(down[j] == 0)
            cur--;
    }

    for(pii j: adj[v]){
        add(j.ff);
    }
}

void remove(int v){
    for(int j: mns[v]){
        if(down[j] == 0)
            cur++;
        up[j]--;
        down[j]++;
        if(up[j] == 0)
            cur--;
    }

    for(pii j: adj[v])
        remove(j.ff);
}



void dfs2(int v){
    for(int j: mns[v]){
        if(up[j] == 0)
            cur++;
        up[j]++;
        down[j]--;
        if(down[j] == 0)
            cur--;
    }
    if(adj[v].size() == 0) return;

    for(int j = 1; j < adj[v].size(); j++){
        add(adj[v][j].ff);
    }
    
    if(cur >= k){
        ans.push_back(adj[v][0].ss);
    }
    dfs2(adj[v][0].ff);

    for(int i = 1; i < adj[v].size(); i++){
        remove(adj[v][i].ff);
        if(cur >= k){
            ans.push_back(adj[v][i].ss);
        }
        dfs2(adj[v][i].ff);
    }
}







int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n>>m>>k;

    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin>>a>>b;
        adj[a].push_back({b, i + 1});
        adj[b].push_back({a, i + 1});
    }

    for(int i = 0; i < m; i++){
        int s;
        cin>>s;
        for(int j = 0; j < s; j++){
            int v;
            cin>>v;
            mns[v].push_back(i);
        }
        down[i] = s;
    }

    dfs(1, -1);
    dfs2(1);
    sort(ans.begin(), ans.end());

    cout<<ans.size()<<endl;
    for(int i: ans)
        cout<<i<<" ";


    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(int, int)':
railway.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i = 0; i < adj[v].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
railway.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i = 1; i < adj[v].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
railway.cpp: In function 'void dfs2(int)':
railway.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int j = 1; j < adj[v].size(); j++){
      |                    ~~^~~~~~~~~~~~~~~
railway.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i = 1; i < adj[v].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~

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