oj.uz

답안 #956942

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
956942 2024-04-02T17:40:57 Z NourWael Firefighting (NOI20_firefighting) C++17
62 / 100
 3000 ms 106068 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);
  }
}
bool f = 1;
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;
    if(reach[it.first]<d+it.second) continue;
    reach[it.first] = d+it.second;
    vis[it.first] = 1;
    if(f) 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;
   int mini = 1e18;
   for(int i=1; i<=n+1; i++) reach[i] = 1e18;
   for(int i = 0; i<n-1; i++) {
    int x,y,c; cin>>x>>y>>c; mini = min(mini, c);
    adj[x].push_back({y,c}), adj[y].push_back({x,c});
   }   
   if(mini*2>k) f = 0;
   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 520 ms 100420 KB Output is correct
2 Correct 477 ms 101032 KB Output is correct
3 Correct 166 ms 47040 KB Output is correct
4 Correct 475 ms 99760 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 14680 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 4 ms 15200 KB Output is correct
6 Correct 3 ms 14680 KB Output is correct
7 Correct 3 ms 14680 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 3 ms 14828 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 2 ms 14684 KB Output is correct
14 Correct 3 ms 14684 KB Output is correct
15 Correct 3 ms 14780 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 2 ms 14816 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14824 KB Output is correct
5 Correct 3 ms 14680 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 2 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 14820 KB Output is correct
12 Correct 3 ms 14680 KB Output is correct
13 Correct 3 ms 14684 KB Output is correct
14 Correct 3 ms 14680 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 3 ms 14820 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 3 ms 14684 KB Output is correct
20 Correct 3 ms 14684 KB Output is correct
21 Correct 3 ms 14684 KB Output is correct
22 Correct 3 ms 14684 KB Output is correct
23 Correct 3 ms 14684 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
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 504 ms 101620 KB Output is correct
2 Correct 277 ms 61692 KB Output is correct
3 Correct 242 ms 64036 KB Output is correct
4 Correct 214 ms 57096 KB Output is correct
5 Correct 3 ms 14680 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 431 ms 96520 KB Output is correct
8 Correct 409 ms 96348 KB Output is correct
9 Correct 404 ms 97024 KB Output is correct
10 Correct 436 ms 100272 KB Output is correct
11 Correct 513 ms 101556 KB Output is correct
12 Correct 292 ms 71792 KB Output is correct
13 Correct 199 ms 49600 KB Output is correct
14 Correct 284 ms 68028 KB Output is correct
15 Correct 375 ms 78008 KB Output is correct
16 Correct 441 ms 83640 KB Output is correct
17 Correct 331 ms 73664 KB Output is correct
18 Correct 345 ms 73296 KB Output is correct

Subtask #5
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 14932 KB Output is correct
2 Correct 6 ms 15084 KB Output is correct
3 Correct 4 ms 14940 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 15 ms 17380 KB Output is correct
6 Correct 20 ms 17492 KB Output is correct
7 Correct 15 ms 17244 KB Output is correct
8 Correct 14 ms 17240 KB Output is correct
9 Correct 12 ms 17240 KB Output is correct
10 Correct 13 ms 17240 KB Output is correct
11 Correct 20 ms 17356 KB Output is correct
12 Correct 4 ms 14940 KB Output is correct
13 Correct 14 ms 17244 KB Output is correct
14 Correct 12 ms 17340 KB Output is correct
15 Correct 6 ms 17244 KB Output is correct
16 Correct 4 ms 14940 KB Output is correct
17 Correct 4 ms 14768 KB Output is correct
18 Correct 6 ms 17244 KB Output is correct
19 Correct 4 ms 14940 KB Output is correct
20 Correct 4 ms 14828 KB Output is correct
21 Correct 7 ms 17240 KB Output is correct

Subtask #6
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 504 ms 97300 KB Output is correct
2 Correct 481 ms 93392 KB Output is correct
3 Correct 504 ms 97724 KB Output is correct
4 Correct 245 ms 54928 KB Output is correct
5 Execution timed out 3050 ms 106068 KB Time limit exceeded
6 Halted 0 ms 0 KB -