제출 #1004291

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1004291		vjudge1	Railway (BOI17_railway)	C++17	0 / 100	1052 ms	179016 KiB

railway

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define f first
#define s second
#define pb push_back
#define pf push_front
#define pi pair<int,int>
#define vi vector<int>
const int MAX = 1e6+10;
int d[MAX];
//vi up[MAX];
vi g[MAX];
set<int> val[MAX];
 map<pi,int>mp;
 const int lmax= 30;
int up[MAX][40];
int timer;
int tin[MAX], tout[MAX];
set<int>st;
vector<int>add[MAX];
vector<int>del[MAX];
  vi cnt;
  
void dfs(int from, int p, int dep){
    d[from]= dep;
    up[from][0]=p;
    tin[from] =++timer;
   // cout << " T " <<timer<<endl;
    for(int i =1 ; i <= lmax; i++){
        up[from][i]= up[up[from][i-1]][i-1];
    }
    
    
    for(int to : g[from]){
        if(to==p) continue;
       // cout << "f " << from<<endl;
        dfs(to,from,dep+1);
    }
    tout[from]=++timer;
}


bool is_ancestor(int a, int b){
    return tin[a]<=tin[b] && tout[a]>= tout[b];
}


int lca(int u, int v){
    //cout <<"U "<< u <<  " " << tin[u]<< " " << tout[u]<<endl;
    //cout << "V "<< v << " " << tin[v]<< " " << tout[v]<<endl;
    if(is_ancestor(u,v)) return u;
    else if(is_ancestor(v,u)) return v;
    //cout <<u << " " << v<< " SDA"<<endl;
    for(int i = lmax; i >= 0; i--){
       // cout << u << endl;
        if(!is_ancestor(up[u][i], v)) u = up[u][i];
    }
    return up[u][0];
}


set<int> dfs2(int from, int p){
    set<int>h;
    set<int>r;
    for(int to : g[from]){
       
        if(to==p) continue;
        
        r = dfs2(to,from);
       /*  cout << to << " " << from<<endl;
         for(int i : r){
             cout << i << " ";
         }
        // cout <<endl<<"R: "<< r.size()<< " "<<mp[{from,to}]<<" "<< mp[{to,from}]<<endl;
         //cout << endl<<endl;
         */
         int a = from, b= to;
     
        cnt[mp[{from,to}]] =r.size();
        cnt[mp[{to,from}]] = r.size();
        if(h.size() > r.size()){
            swap(h,r);
        }
        for(int i : r){
            h.insert(i);
        }
        
    }
    for(int i : add[from]){
        h.insert(i);
    }
    for(int i : del[from]){
        h.erase(i);
    }
    return h;
}

int main(){
    int n,m,k;
    cin >> n>>m>>k;
    pi coor[n];
cnt.resize(n);
   
    ll a,b;
   
    
    for(int i = 1; i < n; i++){
        cin >> a >>b;
        if(a>b)swap(a,b);
        mp[{a,b}]= i;
        mp[{b,a}]=i;
        g[a].pb(b);
        g[b].pb(a);
        coor[i]={a,b};
    }
    
    
    dfs(1,1,0);
    
    int q;
    int ind = 1;
    for(int i =0 ; i < m; i++){
          cin >> q;
         vector<pi> ord;
         for(int i = 0; i < q; i++){
            
             cin >> a;
            
             ord.pb({d[a],a});
         }
         sort(ord.begin(),ord.end());
         for(int j  = 0; j < q; j++){
            for(int k = j+1; k < q; k++){
                int h = ord[j].s;
                
                int p = ord[k].s; 
               // cout << h << "  " << p<< " " << lca(h,p)<<endl;
                //cout << "IND: " <<ind<<endl;
                add[h].pb(ind);
                add[p].pb(ind);
                del[lca(h,p)].pb(ind);
                
                
              
            }
         }
         ind++;
    }
    
    
    dfs2(1,-1);
    
    vi ans;
    for(int i =1; i < n;i++){
        if(cnt[mp[coor[i]]]>=k){
        
        //    cout << coor[i].f << " "<< coor[i].s << " " << mp[coor[i]]<<endl;
            ans.pb(i);
        }
    }
    
    sort(ans.begin(),ans.end());
    cout << ans.size() << endl;
    for(int i : ans){
        cout << i << " ";
    }
    cout << endl;
        
}

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

railway.cpp: In function 'std::set<int> dfs2(int, int)':
railway.cpp:78:14: warning: unused variable 'a' [-Wunused-variable]
   78 |          int a = from, b= to;
      |              ^
railway.cpp:78:24: warning: unused variable 'b' [-Wunused-variable]
   78 |          int a = from, b= to;
      |                        ^

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