Submission #1024369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024369		vjudge1	Friend (IOI14_friend)	C++17	23 / 100	6 ms	4612 KiB

friend

#include "friend.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>adj[100100],onsie;
int dep[100100],match[100100],col[100100];
bitset<100100>vis;
void AE(int x,int y){
    x++,y++;
    adj[x].push_back(y);
    adj[y].push_back(x);
}
int bfs(int n){
    queue<int>q;
    for(auto i:onsie)
        if(!match[i])
            q.push(i),
            dep[i]=1;
        else dep[i]=0;
    dep[0]=0;
    while(q.size()){
        int x=q.front();
        q.pop();
        if(dep[x]>=dep[0]&&dep[0])
            continue;
        for(auto i:adj[x])
            if(!dep[match[i]])
                dep[match[i]]=dep[x]+1,
                q.push(match[i]);
    }
    return dep[0];
}
int dfs(int n){
    if(!n)return 1;
    for(auto i:adj[n]){
        if(dep[match[i]]==dep[n]+1&&dfs(match[i]))
            return match[match[n]=i]=n,1;
    }
    dep[n]=1e9;
    return 0;
}
void dfsc(int i){
    if(col[i])onsie.push_back(i);
    vis[i]=1;
    for(auto n:adj[i]) if(!vis[n])
        col[n]=!col[i],dfsc(n);
    else assert(col[n]^col[i]);
}
int runmatch(int n){
    for(int i=1;i<=n;i++)
        if(!vis[i])
            dfsc(i);
    int ans=0;
    while(bfs(n))for(auto i:onsie)
        if(!match[i]) ans+=dfs(i);
    return ans;
}
int amatching(int host[],int protoc[],int n){
    for(int i=1;i<n;i++){
        cerr<<i <<" done\n";
        if(i==244){
            cerr<<" hmm";
        }
        if(protoc[i])
            for(auto x:adj[host[i]+1])
                AE(x-1,i);
        else AE(i,host[i]);
    }
    return n-runmatch(n);
}
int findSample(int n,int confidence[],int host[],int protocol[]){
    /*if(n<=10) return bruteforce(n,confidence,host,protocol);
    set<int>st;
    int ans=0,ans2=0;
    for(int i=0;i<n;i++)
        ans+=confidence[i],ans2=max(ans2,confidence[i]);
    for(int i=1;i<n;i++)
        st.insert(protocol[i]);
    if(st.size()==1)
	    return protocol[1]==1?ans:protocol[1]?ans2:itsatree(host,confidence,n);*/
    return amatching(host,protocol,n);
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 19
• Subtask 5: 23 / 23
• Subtask 6: 0 / 31