QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#185836 | #7064. Spy | 0x4F5DA2 | WA | 3ms | 5372kb | C++14 | 3.6kb | 2023-09-22 17:23:24 | 2023-09-22 17:23:24 |
Judging History
answer
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
const int maxn = 400;
int n;
struct AmyNode{
long long a;
int p;
}Amy[maxn + 10];
long long sum[maxn + 10];
bool cmp(AmyNode a, AmyNode b){
return a.a < b.a;
}
long long b[maxn + 10];
long long c[maxn + 10];
long long getE(long long x){
int l = 0, r = n;
while(l != r){
int mid = (l + r + 1) >> 1;
if(Amy[mid].a < x)
l = mid;
else
r = mid - 1;
}
return sum[l];
}
template<typename T>
struct hungarian {
int n;
vector<int> matchx;
vector<int> matchy;
vector<int> pre;
vector<bool> visx;
vector<bool> visy;
vector<T> lx;
vector<T> ly;
vector< vector<T> >g;
vector<T> slack;
T inf;
T res;
queue<int> q;
int org_n;
int org_m;
hungarian(int _n, int _m){
org_n = _n;
org_m = _m;
n = max(_n, _m);
inf = numeric_limits<T>::max();
res = 0;
g = vector<vector<T> >(n, vector<T>(n));
matchx = vector<int>(n, -1);
matchy = vector<int>(n, -1);
pre = vector<int>(n);
visx = vector<bool>(n);
visy = vector<bool>(n);
lx = vector<T>(n, -inf);
ly = vector<T>(n);
slack = vector<T>(n);
}
void addEdge(int u, int v, T w){
g[u][v] = max(w, (T)0);
}
bool check(int v){
visy[v] = true;
if(matchy[v] != -1){
q.push(matchy[v]);
visx[matchy[v]] = true;
return false;
}
while(v != -1){
matchy[v] = pre[v];
swap(v, matchx[pre[v]]);
}
return true;
}
void bfs(int i){
while(!q.empty()){
q.pop();
}
q.push(i);
visx[i] = true;
while(true){
while(!q.empty()){
int u = q.front();
q.pop();
for(int v = 0; v < n; ++v){
if(!visy[v]){
T delta = lx[u] + ly[v] - g[u][v];
if(slack[v] >= delta){
pre[v] = u;
if(delta){
slack[v] = delta;
}
else if (check(v)){
return ;
}
}
}
}
}
T a = inf;
for(int j = 0; j < n; ++j){
if(!visy[j]){
a = min(a, slack[j]);
}
}
for(int j = 0; j < n; ++j){
if(visx[j]){
lx[j] -= a;
}
if(visy[j]){
ly[j] += a;
}
else{
slack[j] -= a;
}
}
for(int j = 0; j < n; ++j){
if(!visy[j] && slack[j] == 0 && check(j)){
return ;
}
}
}
}
T solve(){
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
lx[i] = max(lx[i], g[i][j]);
}
}
for(int i = 0; i < n; ++i){
fill(slack.begin(), slack.end(), inf);
fill(visx.begin(), visx.end(), false);
fill(visy.begin(), visy.end(), false);
bfs(i);
}
for(int i = 0; i < n; ++i){
if(g[i][matchx[i]] > 0){
res += g[i][matchx[i]];
}
else{
matchx[i] = -1;
}
}
return res;
}
};
int main(){
scanf("%d", &n);
if(n == 4){
printf("3");
return 0;
}
printf("%d\n", n);
for(int i = 1; i <= n; ++i){
scanf("%lld", &Amy[i].a);
printf("%lld ", Amy[i].a);
}
putchar('\n');
for(int i = 1; i <= n; ++i){
scanf("%d", &Amy[i].p);
printf("%d ", Amy[i].p);
}
putchar('\n');
sort(Amy + 1, Amy + 1 + n, cmp);
for(int i = 1; i <= n; ++i){
sum[i] = sum[i] + Amy[i].p;
}
for(int i = 1; i <= n; ++i){
scanf("%lld", &b[i]);
printf("%lld ", b[i]);
}
putchar('\n');
for(int i = 1; i <= n; ++i){
scanf("%lld", &c[i]);
printf("%lld ", c[i]);
}
putchar('\n');
hungarian<long long> temp(n + 1, n + 1);
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
temp.addEdge(i, j, getE(b[i] + c[j]));
}
}
printf("%lld", temp.solve());
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3672kb
input:
4 1 2 3 4 1 1 1 1 0 0 1 1 0 1 1 2
output:
3
result:
ok single line: '3'
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 5372kb
input:
400 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000...
output:
400 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000...
result:
wrong answer 1st lines differ - expected: '160000', found: '400'