oj.uz

Submission #239883

# Submission time Handle Problem Language Result Execution time Memory
239883 2020-06-17T12:42:31 Z LittleFlowers__ Friend (IOI14_friend) C++17
69 / 100
 37 ms 2936 KB 
#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
#define gg exit(0);

//#define unx

#ifndef unx
#include "friend.h"
#endif // unx

const int N=1010;

int dd[N],pos[N],x[N],y[N];
vector<int> ad[N];

void add(int i,int j){
    ad[i].pb(j);
    ad[j].pb(i);
}

void build(int n, int confidence[], int host[], int protocol[]){
    forinc(i,1,n){
        if(protocol[i]!=1)
            forv(j,ad[host[i]])
                add(j,i+1);
        if(protocol[i]!=2)
            add(host[i],i+1);
    }
}

int dfs(int u){
    if(dd[u]) return 0;
    dd[u]=1;
    forv(v,ad[u]) if(!y[v] || dfs(y[v])){
        x[u]=v;
        y[v]=u;
        return 1;
    }
    return 0;
}

void dfs(int u,int c){
    if(pos[u]) return;
    pos[u]=c;
    forv(v,ad[u]) dfs(v,c^1);
}


int confi[1010];

ii dfs1(int u,int p=-1){
    dd[u]=1;
    int f=0, g=confi[u];
    forv(v,ad[u]) if(v!=p){
        int x,y; tie(x,y)=dfs1(v,u);
        f+=max(x,y);
        g+=x;
    }
    return {f,g};
};

int findSample(int n, int confidence[], int host[], int protocol[]){
    int mask=0;
    forinc(i,1,n-1){
        host[i]++;
        protocol[i]=1<<protocol[i];
        mask|=protocol[i];
    }
    forinc(i,1,n) confi[i]=confidence[i-1];
    if(mask==1){
        build(n,confidence,host,protocol);
        int tot=0;
        forinc(i,1,n) if(!dd[i]){
            int x,y; tie(x,y)=dfs1(i);
            tot+=max(x,y);
        }
        return tot;
    }
    if(mask==2){
        int tot=0;
        forinc(i,1,n) tot+=confidence[i-1];
        return tot;
    }
    if(mask==4){
        int tot=0;
        forinc(i,1,n) tot=max(tot,confidence[i-1]);
        return tot;
    }
    if(n<=10){
        build(n,confidence,host,protocol);
        int ret=0;
        forinc(i,1,(1<<n)-1){
            int suc=1, tot=0;
            forinc(j,1,n) if(bit(i,j)){
                forv(t,ad[j]) if(bit(i,t)) suc=0;
                tot+=confidence[j-1];
            }
            if(suc) ret=max(ret,tot);
        }
        return ret;
    }
    if(n<=1000){
        build(n,confidence,host,protocol);
        forinc(i,1,n) if(!pos[i]) dfs(i,2);
        int flow=0;
        forinc(i,1,n) if(pos[i]==2){
            reset(dd,0);
            flow+=dfs(i);
        }
        return n-flow;
    }
}

#ifdef unx
int C[1010],H[1010],P[1010];
main(){
    #define task "friend"
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    int n=in;
    forinc(i,1,n) C[i-1]=in;
    forinc(i,1,n-1) H[i]=in, P[i]=in;
    cout<<findSample(n,C,H,P);
}
#endif

Compilation message

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:129:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 4 ms 384 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Runtime error 37 ms 2936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -