oj.uz

답안 #956875

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
956875 2024-04-02T15:35:17 Z NourWael Firefighting (NOI20_firefighting) C++17
43 / 100
 3000 ms 100788 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std; 
int const mxN = 3e5+5;
int dis[mxN], lift[mxN][20], elem[mxN], n, k, reach[mxN];
vector<pair<int,int>> adj[mxN];
bool vis[mxN];
vector<pair<int,pair<int,int>>> v;

int up ( int steps , int e) {
  for(int i=0; i<=19; i++) 
     if(steps&(1<<i)) e = lift[e][i];
  return e;
}
 
int bring ( int i ) {
  int l = 0, r = n+1, ans = i;
  while(l<=r) {
    int mid = (l+r)/2, e = up(mid, i);
    if(dis[i]-dis[e]<=k) { ans = e, l = mid+1; }
    else r = mid-1;
  }
  return ans;
}

void dfs ( int i , int p, int m) { 
  dis[i] = m;
  lift[i][0] = p;
  for(int j=1; j<20; j++) lift[i][j] = lift[lift[i][j-1]][j-1];
  elem[i] = bring(i);
  v.push_back({-dis[elem[i]], {elem[i], i}});
  for(auto it:adj[i]) {
    if(it.first==p) continue;
    dfs(it.first,i, m+it.second);
  }
}

void do_work ( int i , int p, int d) {
  vis[i] = 1;
  for(auto it:adj[i]) {
    if(it.first==p) continue;
    if(d+it.second>k) continue;
    int left = k-(d+it.second);
    //if(reach[it.first]>=left) continue;
    reach[it.first] = left;
    do_work(it.first, i, d+it.second);
  }
}
signed main() {
  
   ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
   cin>>n>>k;
   for(int i = 0; i<n-1; i++) {
    int x,y,c; cin>>x>>y>>c;
    adj[x].push_back({y,c}), adj[y].push_back({x,c});
   }   
   dfs(1,1,0);
   
   vector<int> fin;
   sort(v.begin(),v.end());
   for(auto it:v) {
     if(!vis[it.second.second]) {
      vis[it.second.second] = 1;
      do_work(it.second.first, 0, 0);
      fin.push_back(it.second.first);
     }
   }

   cout<<fin.size()<<'\n';
   for(auto it:fin) cout<<it<<' ';

   return 0;
  
}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 506 ms 95644 KB Output is correct
2 Correct 478 ms 96176 KB Output is correct
3 Correct 156 ms 44752 KB Output is correct
4 Correct 463 ms 92656 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14680 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 3 ms 14684 KB Output is correct
12 Correct 3 ms 14684 KB Output is correct
13 Correct 3 ms 14680 KB Output is correct
14 Correct 3 ms 14684 KB Output is correct
15 Correct 3 ms 14828 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 3 ms 14680 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 3 ms 14824 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14936 KB Output is correct
8 Correct 4 ms 14684 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 3 ms 14680 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 3 ms 14684 KB Output is correct
14 Correct 3 ms 14684 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 9 ms 14816 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 3 ms 14828 KB Output is correct
19 Correct 3 ms 14816 KB Output is correct
20 Correct 3 ms 14684 KB Output is correct
21 Correct 3 ms 14688 KB Output is correct
22 Correct 3 ms 14680 KB Output is correct
23 Correct 4 ms 14780 KB Output is correct
24 Correct 3 ms 14684 KB Output is correct
25 Correct 3 ms 14684 KB Output is correct
26 Correct 3 ms 14684 KB Output is correct

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 481 ms 95684 KB Output is correct
2 Correct 251 ms 58560 KB Output is correct
3 Correct 249 ms 63832 KB Output is correct
4 Correct 217 ms 57404 KB Output is correct
5 Correct 3 ms 14680 KB Output is correct
6 Correct 3 ms 14680 KB Output is correct
7 Execution timed out 3085 ms 97140 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 14936 KB Output is correct
2 Correct 5 ms 14940 KB Output is correct
3 Correct 4 ms 14940 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 38 ms 17244 KB Output is correct
6 Correct 36 ms 17244 KB Output is correct
7 Correct 25 ms 17244 KB Output is correct
8 Correct 25 ms 17244 KB Output is correct
9 Correct 20 ms 17244 KB Output is correct
10 Correct 20 ms 17240 KB Output is correct
11 Correct 37 ms 17364 KB Output is correct
12 Correct 4 ms 14940 KB Output is correct
13 Correct 26 ms 17496 KB Output is correct
14 Correct 20 ms 17244 KB Output is correct
15 Correct 5 ms 17244 KB Output is correct
16 Correct 4 ms 14940 KB Output is correct
17 Correct 4 ms 14920 KB Output is correct
18 Correct 5 ms 17240 KB Output is correct
19 Correct 7 ms 15064 KB Output is correct
20 Correct 4 ms 14940 KB Output is correct
21 Correct 5 ms 17244 KB Output is correct

Subtask #6
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 489 ms 90092 KB Output is correct
2 Correct 448 ms 86972 KB Output is correct
3 Correct 509 ms 91184 KB Output is correct
4 Correct 216 ms 53272 KB Output is correct
5 Execution timed out 3095 ms 100788 KB Time limit exceeded
6 Halted 0 ms 0 KB -