제출 #1079996

#제출 시각아이디문제언어결과실행 시간메모리
1079996PoPularPlusPlus봉쇄 시간 (IOI23_closing)C++17
0 / 100
1059 ms34116 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define all(x) x.begin(),x.end() #define pb(x) push_back(x) #define mp(x,y) make_pair(x,y) #define vf first #define vs second int max_score(int n, int x, int y, ll k,vector<int> u, vector<int> v, vector<int> w){ vector<pair<int,ll>> adj[n + 1]; for(int i = 0; i < n-1; i++){ adj[u[i]].pb(mp(v[i] , w[i])); adj[v[i]].pb(mp(u[i] , w[i])); } ll dis[n] , path[n] , dis1[n]; memset(dis,-1,sizeof dis); memset(path , -1 , sizeof path); memset(dis1, -1 , sizeof dis1); queue<int> q; q.push(x); dis[x] = 0; path[x] = 0; while(q.size()){ int node = q.front(); q.pop(); for(auto i : adj[node]){ if(dis[i.vf] == -1){ dis[i.vf] = dis[node] + i.vs; path[i.vf] = path[node] + 1; q.push(i.vf); } } } bool vis[n]; memset(vis,0,sizeof vis); vis[y] = 1; ll cur = y; vector<int> path_w; path_w.pb(y); while(cur != x){ for(auto i : adj[cur]){ if(path[i.vf] == path[cur] - 1){ cur = i.vf; vis[i.vf] = 1; path_w.pb(i.vf); break; } } } dis1[y] = 0; q.push(y); while(q.size()){ int node = q.front(); q.pop(); for(auto i : adj[node]){ if(dis1[i.vf] == -1){ dis1[i.vf] = dis1[node] + i.vs; path[i.vf] = path[node] + 1; q.push(i.vf); } } } /* for(int i = 0; i < n; i++){ cout << dis[i] << ' ' << dis1[i] << '\n'; }*/ int weight[n]; priority_queue<pair<ll,int>> pq; for(int i = 0; i < n; i++){ if(vis[i] == 0 && dis[i] < dis1[i]){ pq.push(mp(dis[i],i)); } } int pos = 0; while(pq.size()){ //cout << "former " << ' ' << pq.top().vs << '\n'; weight[pos++] = pq.top().vs; pq.pop(); } int xx = pos; while(path_w.size()){ weight[pos++] = path_w.back(); path_w.pop_back(); } for(int i = 0; i < n; i++){ if(vis[i] == 0 && dis[i] > dis1[i]){ pq.push(mp(dis1[i] , i)); } } int yy = pos -1; vector<int> rev; while(pq.size()){ rev.pb(pq.top().vs); pq.pop(); } while(rev.size()){ //cout << "later " << pq.top().vs << '\n'; weight[pos++] = rev.back(); rev.pop_back(); } for(int i = 0; i < n; i++){ cout << weight[i] << ' '; } cout << '\n'; x = xx; y = yy; cur = 0; int ans = 0; ll cur_w[n]; for(int i = x; i >= 0; i--){ for(int j = y; j < n; j++){ memset(cur_w,0,sizeof cur_w); ll rem = k; ll cur = 0; for(int tp = x; tp >= i; tp--){ rem -= dis[weight[tp]]; //cout << "dis " << dis[weight[tp]] << ' '; cur_w[tp] = dis[weight[tp]]; } cur = 0; for(int tp = y; tp <= j; tp++){ rem -= dis1[weight[tp]]; //cout << "dis1 " << dis1[weight[tp]] << ' '; cur_w[tp] = dis1[weight[tp]]; } //cout << i << ' ' << j << ' ' << rem << endl; if(rem >= 0){ int res = (x - i) + (j - y) + 2; // cout << res << ' '; int left = x + 1 , right = y - 1; ll cur_l = dis[weight[left]] , cur_r = dis1[weight[right]]; while(rem >= 0 && (left < n || right >= 0)){ //cout << rem << ' ' << left << ' ' << right << endl; if(right < 0 || (left < n && cur_l - cur_w[left] < cur_r - cur_w[right])){ if(rem - (max(0LL,cur_l - cur_w[left])) >= 0){ rem -= (max(0LL,cur_l - cur_w[left])); cur_w[left] += (max(0LL,cur_l - cur_w[left])); res++; left++; if(left < n)cur_l = dis[weight[left]]; } else break; } else { if(rem - max(0LL, cur_r - cur_w[right]) >= 0){ rem -= max(0LL, cur_r - cur_w[right]); cur_w[right] += max(0LL, cur_r - cur_w[right]); res++; right--; if(right >= 0)cur_r = dis1[weight[right]]; } else break; } } // cout << i << ' ' << j << ' ' << res << ' ' << rem << ' ' << left << ' ' << right << '\n'; // cout << i << ' ' << j << ' ' << res << ' ' << left << ' ' << right << "\n"; ans = max(ans , res); } } } return ans; }

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

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:132:16: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
  132 |             ll cur = 0;
      |                ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...