CCF 201803-5二次加算

データ規模は比較的大きく,比較的直感的な幅探索アルゴリズムを思いついた.サンプルが合格した.しかし、コミットは20分しかなく、実行はタイムアウトしました.効率の高いアルゴリズムを求める.

#include
#include 
#include
#include
#include
using namespace std;
const int Q = 1000000007;
//const int INF = 1e6+5;//    ，         
struct Edge{
 int from, to;//dist    
 //Edge(int u, int v, int d):from(u),to(v),dist(d){}
 Edge(int u, int v):from(u),to(v){}
};
struct HeapNode{
 int d;//  
 int u;//    
 bool operator < (const HeapNode& rhs) const {
  return d > rhs.d;
 } 
};
struct Tree{
 int n;//      
 vector value;//      
 vector edges;
 vector > G;//    
 
 vector done;    //        
 vector p; //  i     p[i] 
 vector > status;
 vector d;
 
 void init(int n){
  this->n = n;
  value.resize(n); 
  edges.clear();
  G.resize(n, vector());
  
  done.clear();
  p.resize(n);
  status.clear();
  d.clear();
  //p.clear();
 }
 void addEdge(int from, int to){
  edges.push_back(Edge(from, to));
  int m = edges.size();
  G[from].push_back(m-1);
  G[to].push_back(m-1); //    
 }
 void bfs(int root, int end){
  done.clear();
  done.resize(n, false);
  p[root] = -1;
  //p.resize(n, -1);
  queue Q;
  for(int i=0;i Q;
  for(int i=0;i(n,false));
  long long ss = 0;
  for(int i=1;i=L && d[j]<=R && !status[i][j]){
     //cout<>T;
 for(int p=0;p>n>>m>>L>>R;
 Tree S;
 S.init(n+1);
 for(int i=1;i<=n;i++){
  cin>>S.value[i];
 }
 int temp;
 for(int i=1;i>temp;
  S.addEdge(temp,i+1);
 }
 //S.display();
 
 int u,v,d;
 for(int i=0;i>u>>v>>d;
  S.add_d(u,v,d);
  //S.display();
  S.sum(L, R);
 }
 
 }
 
 return 0;
}