이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "friend.h"
//#include "grader.cpp"
#include <vector>
#include <iostream>
using namespace std;
const int MAXN = 1005;
int n;
vector <int> graph[MAXN];
void constructGrahp(int n, int confidence[], int host[], int protocol[])
{
for(int x = 1;x<=n;x++)
{
if(protocol[x]==0)
{
graph[ host[x] ].push_back(x);
graph[x].push_back(host[x]);
}
else if(protocol[x]==1)
{
for(int y: graph[ host[x] ])
{
graph[y].push_back(x);
graph[x].push_back(y);
}
}
else if(protocol[x]==2)
{
graph[x].push_back(host[x]);
graph[ host[x] ].push_back(x);
for(int y: graph[ host[x] ])
{
graph[y].push_back(x);
graph[x].push_back(y);
}
}
}
}
namespace Subtask1
{
bool can(int x, int mask)
{
for(int y: graph[x])
{
if(((mask>>y)&1)==1) return false;
}
return true;
}
int rec(int x, int mask, int confidence[])
{
if(x==n) return 0;
int answer = rec(x+1, mask, confidence);
if(can(x, mask)==true) answer = max(answer, confidence[x]+rec(x+1, (mask|(1<<x)), confidence));
return answer;
}
int solve(int n, int confidence[], int host[], int protocol[])
{
return rec(0, 0, confidence);
}
};
namespace Subtask2
{
int solve(int n, int confidence[], int host[], int protocol[])
{
int ans = 0;
for(int x = 0;x<n;x++) ans += confidence[x];
return ans;
}
};
namespace Subtask3
{
int solve(int n, int confidence[], int host[], int protocol[])
{
int ans = 0;
for(int x = 0;x<n;x++) ans = max(ans, confidence[x]);
return ans;
}
};
int guessSubtask(int n, int confidence[], int host[], int protocol[])
{
if(n<=10) return 1;
bool subtask2 = true;
for(int x = 1;x<n;x++)
{
if(protocol[x]!=1)
{
subtask2 = false;
break;
}
}
if(subtask2==true) return 2;
bool subtask3 = true;
for(int x = 1;x<n;x++)
{
if(protocol[x]!=2)
{
subtask3 = false;
break;
}
}
if(subtask3==true) return 3;
return -1;
}
int findSample(int _n,int confidence[],int host[],int protocol[])
{
int subtask = guessSubtask(n, confidence, host, protocol);
if(subtask==2) return Subtask2::solve(n, confidence, host, protocol);
else if(subtask==3) return Subtask3::solve(n, confidence, host, protocol);
n = _n;
constructGrahp(n, confidence, host, protocol);
if(subtask==1) return Subtask1::solve(n, confidence, host, protocol);
return 0;
}
# | 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... |