이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=1005;
int n,arr[mxn],rel[mxn][mxn],ans=0,dp[mxn][2],color[mxn],mt[mxn],used[mxn];
vector<int>vt[mxn];
vector<int>vt2[mxn];
vector<int>odd,even;
void dfs(int u,int p){
for(int v:vt[u]){
if(v!=p){
dfs(v,u);
dp[u][0]+=dp[v][1];
dp[u][1]+=max(dp[v][0],dp[v][1]);
}
}
dp[u][0]+=arr[u];
ans=max(ans,dp[u][0]);
ans=max(ans,dp[u][1]);
}
void dfs2(int u,int dep){
if(dep%2==0){
even.pb(u);
}
else{
odd.pb(u);
}
color[u]=1;
for(int v:vt[u]){
if(color[v]) continue;
dfs2(v,dep+1);
}
}
bool kuhn(int u){
if(used[u]) return false;
used[u]=1;
for(int v:vt2[u]){
if(mt[v]==-1||kuhn(mt[v])){
mt[v]=u;
return true;
}
}
return false;
}
int solve(){
dfs2(1,0);
int x=even.size();
int y=odd.size();
int num=0;
for(int u:even){
num++;
for(int j=0;j<odd.size();j++){
int v=odd[j];
if(rel[u][v]){
vt2[num].pb(j+1);
}
}
}
for(int i=1;i<=y;i++){
mt[i]=-1;
}
for(int i=1;i<=x;i++){
memset(used,0,sizeof(used));
kuhn(i);
}
ans=0;
for(int i=1;i<=y;i++){
if(mt[i]!=-1) ans++;
}
return n-ans;
}
int findSample(int N,int confidence[],int host[],int protocol[]){
n=N;
for(int i=0;i<n;i++){
arr[i+1]=confidence[i];
}
bool task2=true,task3=true,task4=true,task5=true;
for(int i=1;i<n;i++){
int type=protocol[i];
if(type!=1) task2=false;
if(type!=2) task3=false;
if(type!=0) task4=false;
if(type==2) task5=false;
}
for(int i=1;i<=n;i++){
if(arr[i]>1) task5=false;
}
if(task2){
int mx=0;
for(int i=1;i<=n;i++){
mx+=arr[i];
}
return mx;
}
if(task3){
int mx=0;
for(int i=1;i<=n;i++){
mx=max(mx,arr[i]);
}
return mx;
}
for(int i=1;i<n;i++){
int node=host[i]+1;
int type=protocol[i];
if(type==0){
vt[node].pb(i+1);
vt[i+1].pb(node);
}
else if(type==1){
int sz=vt[node].size();
for(int j=0;j<sz;j++){
int v=vt[node][j];
vt[v].pb(i+1);
vt[i+1].pb(v);
}
}
else{
int sz=vt[node].size();
for(int j=0;j<sz;j++){
int v=vt[node][j];
vt[v].pb(i+1);
vt[i+1].pb(v);
}
vt[node].pb(i+1);
vt[i+1].pb(node);
}
}
for(int i=1;i<=n;i++){
for(int v:vt[i]){
rel[i][v]=1;
}
}
return solve();
if(task4){
dfs(1,-1);
return ans;
}
ans=0;
for(int mask=1;mask<(1<<n);mask++){
vector<int>v;
int sum=0;
for(int i=0;i<n;i++){
if(mask&(1<<i)){
v.pb(i+1);
sum+=arr[i+1];
}
}
bool ok=true;
for(int i=0;i<v.size();i++){
for(int j=i+1;j<v.size();j++){
if(rel[v[i]][v[j]]){
ok=false;
}
}
}
if(ok) ans=max(ans,sum);
}
return ans;
}
/*
g++ friend.cpp grader.cpp ; .\a.exe
6
13 3 6 20 10 15
0 0
0 1
1 2
2 1
0 0
6
1 1 1 1 1 1
0 0
0 0
1 0
1 0
1 1
*/
컴파일 시 표준 에러 (stderr) 메시지
friend.cpp: In function 'int solve()':
friend.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int j=0;j<odd.size();j++){
| ~^~~~~~~~~~~
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:160:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
160 | for(int i=0;i<v.size();i++){
| ~^~~~~~~~~
friend.cpp:161:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
161 | for(int j=i+1;j<v.size();j++){
| ~^~~~~~~~~
friend.cpp:88:43: warning: variable 'task5' set but not used [-Wunused-but-set-variable]
88 | bool task2=true,task3=true,task4=true,task5=true;
| ^~~~~
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |