| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 420987 | marcipan5000 | Friend (IOI14_friend) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
bool q1=1,q2=1,q3=1;
int n1;
int ans=0;
int uu;
int conff[1002];
vector<int> t[1002];
bool z[15];
int w=0;
void rek(int p) {
if (p==n1) {
for (int i=0;i<n1;i++) {
if (z[i]==1) {
for (int j=0;j<t[i].size();j++) {
if (z[t[i][j]]==1) {
return;
}
}
}
}
ans=max(ans,w);
return;
}
z[p]=0;
rek(p+1);
z[p]=1; w+=conff[p];
rek(p+1);
z[p]=0; w-=conff[p];
return;
}
const int maxn = (int)1e3;
vector<bool> volt;
vector<int> par;
bool javit(int akt, bool p){
volt[akt] = true;
if(par[akt] != -1 && p)
return javit(par[akt], !p);
for(int x : t[akt]){
if(!volt[x] && (par[x] == -1 || javit(x, !p))){
par[akt] = x;
par[x] = akt;
return true;
}
}
return false;
}
int subtask5(int n){
par.assign(n, -1);
int maxmatching = 0;
for(int i = 0; i < n; i++){
volt.assign(n, false);
if(par[i] == -1 && javit(i, false))
maxmatching++;
}
return n-maxmatching;
}
bool vo[1002];
pair<int,int> z2;
pair<int,int> dfs(int p) {
vo[p]=1;
pair<int,int> ans;
ans.first=0;
ans.second=0;
for (int i=0;i<t[p].size;i++) {
if (vo[t[p][i]]==0) {
z2=dfs(t[p][i]);
ans.second=max(ans.second,z2.first);
ans.first=max(ans.first,z2.first);
ans.first=max(ans.first,z2.second+coeff[p]);
}
}
return(ans);
}
int findSample(int n,int confidence[],int host[],int protocol[]) {
n1=n;
for (int i=1;i<n;i++) {
if (protocol[i]!=0) {
q1=0;
}
if (protocol[i]!=1) {
q2=0;
}
if (protocol[i]!=2) {
q3=0;
}
}
if (q3==1) {
int ma=0;
for (int i=0;i<n;i++) {
ma=max(ma,confidence[i]);
}
return(ma);
}
if (q2==1) {
int ma=0;
for (int i=0;i<n;i++) {
ma=ma+confidence[i];
}
return(ma);
}
if (q1==1) {
z2=rek(0);
return(max(z2.first,z2.second));
}
for (int i=0;i<n;i++) {
conff[i]=confidence[i];
}
for (int i=1;i<n;i++) {
if (protocol[i]==0) {
t[i].push_back(host[i]);
t[host[i]].push_back(i);
}
if (protocol[i]==1) {
uu=t[host[i]].size();
for (int j=0;j<uu;j++) {
t[i].push_back(t[host[i]][j]);
t[t[host[i]][j]].push_back(i);
}
}
if (protocol[i]==2) {
uu=t[host[i]].size();
for (int j=0;j<uu;j++) {
t[i].push_back(t[host[i]][j]);
t[t[host[i]][j]].push_back(i);
}
t[i].push_back(host[i]);
t[host[i]].push_back(i);
}
}
if (n<=10) {
/*
for (int i2=0;i2<=i;i2++) {
for (int j=0;j<t[i2].size();j++) {
cout << t[i2][j] << " ";
}
cout << endl;
}
cout << endl;
*/
rek(0);
return(ans);
}
return(subtask5(n));
}