oj.uz

Submission #244688

# Submission time Handle Problem Language Result Execution time Memory
244688 2020-07-04T15:17:52 Z kimbj0709 Railway (BOI17_railway) C++14
29 / 100
 117 ms 39020 KB 
#include<bits/stdc++.h>
using namespace std;
#define maxn 100050
vector<vector<pair<int,int> > > adj(maxn);
vector<int> cnt(maxn,0);
vector<int> vect1;
vector<int> seg(maxn*20,0);
vector<int> depth(maxn,INT_MAX);
vector<int> pos(maxn);
int no_of_vertex,no_of_people,mini;
void build(int node,int start,int end){
  if(start==end){
    seg[node] = vect1[start];
    return;
  }
  int mid = (start+end)/2;
  build(node*2+1,start,mid);
  build(node*2+2,mid+1,end);
  int l = seg[node*2+1],r=seg[node*2+2];
  if(depth[l]<depth[r]){
    seg[node] = l;
  }
  else{
    seg[node] = r;
  }
}
int query(int node,int start,int end,int rangemin,int rangemax){
  //cout << node << " " << start << " " << end << " "<< rangemin << " " << rangemax << " " << seg[node] << endl;
  if(start>rangemax||end<rangemin){
    return -1;
  }
  if(start>=rangemin&&end<=rangemax){
    return seg[node];
  }
  int mid = (start+end)/2;
  int a = query(node*2+1,start,mid,rangemin,rangemax);
  int b = query(node*2+2,mid+1,end,rangemin,rangemax);
  if(a==-1){
    return b;
  }
  else if(b==-1){
    return a;
  }
  if(depth[a]<depth[b]){
    return a;
  }
  else{
    return b;
  }
}
void dfs(int node,int parent,int d){
    pos[node] = (int)vect1.size();
    vect1.push_back(node);
    depth[node] = d;
    for(auto k:adj[node]){
        if(k.first!=parent){
            vect1.push_back(node);
            dfs(k.first,node,d+1);
        }
    }
}
vector<int> ans;
void dfs2(int node,int parent,int last){
    for(auto k:adj[node]){
        if(k.first!=parent){
            dfs2(k.first,node,k.second);
            cnt[node] += cnt[k.first];
        }
    }
    if(cnt[node]>=mini){
        ans.push_back(last);
    }
}
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int no_of_input;
    int input1,input2,input3,input;
    cin >> no_of_vertex >> no_of_people >> mini;
    for(int i=0;i<no_of_vertex-1;i++){
        cin >> input1 >> input2;
        adj[input1].push_back({input2,i});
        adj[input2].push_back({input1,i});
    }
    dfs(1,-1,0);
    build(0,0,vect1.size()-1);
    for(int i=0;i<no_of_people;i++){
        cin >> no_of_input >> input1 >> input2;
        assert(no_of_input==2);
        int lca = query(0,0,vect1.size()-1,min(pos[input1],pos[input2]),max(pos[input1],pos[input2]));

        cnt[input1]++;
        cnt[input2]++;
        cnt[lca] -= 2;
    }
    /*for(int i=1;i<=no_of_vertex;i++){
        for(int j=1;j<=no_of_vertex;j++){
            cout << i << " " << j << " " << query(0,0,vect1.size()-1,min(pos[i],pos[j]),max(pos[i],pos[j])) << "\n";
        }
    }*/
    dfs2(1,-1,-1);
    /*for(int i=1;i<=no_of_vertex;i++){
        cout << cnt[i] << " ";
    }*/
    sort(ans.begin(),ans.end());
    cout << ans.size() << '\n';
    for(auto k:ans){
        cout << k+1 << " ";
    }


}

Compilation message

railway.cpp: In function 'int32_t main()':
railway.cpp:78:23: warning: unused variable 'input3' [-Wunused-variable]
     int input1,input2,input3,input;
                       ^~~~~~
railway.cpp:78:30: warning: unused variable 'input' [-Wunused-variable]
     int input1,input2,input3,input;
                              ^~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11648 KB Output is correct
2 Runtime error 30 ms 24696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11648 KB Output is correct
2 Runtime error 30 ms 24696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 24684 KB Output is correct
2 Runtime error 26 ms 23552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 20144 KB Output is correct
2 Correct 96 ms 17008 KB Output is correct
3 Correct 99 ms 16552 KB Output is correct
4 Correct 117 ms 16624 KB Output is correct
5 Correct 109 ms 16624 KB Output is correct
6 Correct 88 ms 20204 KB Output is correct
7 Correct 94 ms 20204 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 20144 KB Output is correct
2 Correct 96 ms 17008 KB Output is correct
3 Correct 99 ms 16552 KB Output is correct
4 Correct 117 ms 16624 KB Output is correct
5 Correct 109 ms 16624 KB Output is correct
6 Correct 88 ms 20204 KB Output is correct
7 Correct 94 ms 20204 KB Output is correct
8 Runtime error 77 ms 39020 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11648 KB Output is correct
2 Runtime error 30 ms 24696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -