제출 #639851

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
639851		Cookie	Railway (BOI17_railway)	C++14	100 / 100	241 ms	45672 KiB

railway

#include<bits/stdc++.h>

using namespace std;
#include<fstream>

#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
typedef unsigned long long ull;
#define pii pair<int, int>
#define pll pair<ll, ll>
#include<fstream>
ifstream fin("disrupt.in");
ofstream fout("disrupt.out");
const ll mod = 1e9 + 7;


const int mxn = 1e5, mxm = 5e4, mxlg = 17;
const int inf = 1e9 + 3;
int n, m, k;
vt<pii>adj[mxn + 1];
int cnt[mxn + 1]; 
set<int>val[mxn + 1];
int up[mxn + 1][17], d[mxn + 1];
vt<int>Lca[mxn + 1];
vt<int>res;
void dfs(int s, int pre){
    for(auto i: adj[s]){
        if(i.fi == pre)continue;
        d[i.fi] = d[s] + 1; up[i.fi][0] = s;
        dfs(i.fi, s);
    }
}
int lca(int a, int b){
    if(d[a] < d[b])swap(a, b);
    int k = d[a] - d[b];
    forr(i, 0, mxlg){
        if(k & (1 << i)){
            a = up[a][i];
        }
    }
    if(a == b)return(a);
    dorr(i, mxlg - 1, 0){
        if(up[a][i] != up[b][i]){
            a = up[a][i]; b = up[b][i];
        }
    }
    return(up[a][0]);
}
void dfs2(int s, int pre){
    for(auto i: adj[s]){
    
        int v = i.fi, id = i.se;
        if(v == pre)continue;
        dfs2(v, s);
        if(val[v].size() >= k){
            res.pb(id);
        }
        if(val[s].size() < val[v].size())swap(val[s], val[v]);
        for(auto j: val[v]){
            val[s].insert(j);
        }
    }
    
    for(auto i: Lca[s]){
        val[s].erase(i);
    }
    
}
int main(){
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    forr(i, 1, n){
        int u, v; cin >> u >> v;
        adj[u].pb({v, i}); adj[v].pb({u, i});
    }
    dfs(1, -1);
    forr(i, 1, mxlg){
        forr(j, 1, n + 1){
            up[j][i] = up[up[j][i - 1]][i - 1];
        }
    }
    forr(i, 0, m){
        int s, v; cin >> s >> v;
        val[v].insert(i);
        forr(j, 1, s){
            int x; cin >> x;
            val[x].insert(i);
            v = lca(v, x);
        }
        Lca[v].pb(i);
        
    }
    dfs2(1, -1);
    cout << res.size() << "\n";
    sort(res.begin(), res.end());
    for(int i = 0 ; i < res.size(); i++)cout << res[i] << ' ';
    
}

컴파일 시 표준 에러 (stderr) 메시지

railway.cpp: In function 'void dfs2(int, int)':
railway.cpp:60:26: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |         if(val[v].size() >= k){
      |            ~~~~~~~~~~~~~~^~~~
railway.cpp: In function 'int main()':
railway.cpp:101:23: 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 = 0 ; i < res.size(); i++)cout << res[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