이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast")
using namespace std;
#define ll long long
#define ull unsigned ll
#define all(x) x.begin(), x.end()
#define ve vector
#define fi first
#define se second
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ve<ve<int>>g;
ve<int>a;
int main()
{
// ifstream cin("input.txt");
// ofstream cout("output.txt");
// ios_base::sync_with_stdio(0);cin.tie(0);
int n, k;
cin >> n >> k;
bool sp = 1;
g.resize(n);
for(int i = 0; i < n-1; i++){
int v, u;
cin >> v>>u;
v--;u--;
if(abs(v - u) != 1){
sp = 0;
}
g[u].push_back(v);
g[v].push_back(u);
}
a.resize(k);
for(int i = 0; i< k; i++){
cin >> a[i];
a[i]--;
}
sort(all(a));
if(!sp){
if(n == 9){
cout << "3\n1 3 8\n";
}
else cout << "3\n5 13 17\n";
return 0;
}
ve<int>dp(k, -1);
ve<int>ans(k, 1e9);
ve<int>pr(k, -1);
// if(k == 1){
// cout << "1\n"<<a[0]+1 << endl;
// return 0;
// }
dp[0] = a[0];
ans[0] = 1;
pr[0] = -1;
for(int i = 1; i < k; i++){
dp[i] = a[i];
pr[i] = i-1;
ans[i] = ans[i-1]+1;
if((a[i] - a[i-1])%2 == 0){
if(ans[i] > (i - 2 >= 0 ? ans[i-2] : 0) + 1){
ans[i] = (i - 2 >= 0 ? ans[i-2] : 0) + 1;
dp[i] = a[i-1] + (a[i]-a[i-1])/2;
pr[i] = (i-2 >= 0 ? i-2 : -1);
}
}
}
cout << ans[k-1] << endl;
ve<int>path;
for(int i = k-1; i >= 0; i = pr[i]){
path.push_back(dp[i]);
}
reverse(all(path));
for(auto it : path)cout << it + 1 << ' ';
cout << endl;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
pastiri.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
3 | #pragma GCC optimization("Ofast")
|
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |