Submission #864838

#	Time	Username	Problem	Language	Result	Execution time	Memory
864838		andrei_boaca	Carnival Tickets (IOI20_tickets)	C++17	39 / 100	3063 ms	101516 KiB

tickets

#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll INF=1e18;
ll ans=0;
int n,m;
vector<vector<int>> sol,v;
bool comp(pll a, pll b)
{
    return a.second>b.second;
}
int S,D,mns,pls;
ll cap[2005][2005],nodes,dist[2005],from[2005],l[2005],r[2005],real_d[2005],old_d[2005];
vector<ll> muchii[2005];
bool use[2005];
int flow;
ll k;
void bellman()
{
    for(int i=0;i<=nodes;i++)
    {
        dist[i]=INF;
        old_d[i]=INF;
        from[i]=-1;
    }
    old_d[S]=0;
    queue<int> coada;
    coada.push(S);
    while(!coada.empty())
    {
        ll nod=coada.front();
        coada.pop();
        for(int i:muchii[nod])
            if(cap[nod][i]>0)
            {
                ll cost=0;
                if(nod==mns)
                {
                    if(i>=0&&i<n)
                        cost=-v[i][m-(k-cap[nod][i])-1];
                }
                if(nod==pls)
                {
                    if(i>=0&&i<n)
                        cost=v[i][k-cap[nod][i]];
                }
                if(nod>=0&&nod<n)
                {
                    if(i==mns)
                        cost=v[nod][m-cap[nod][i]];
                    if(i==pls)
                        cost=-v[nod][cap[nod][i]-1];
                }
                if(old_d[i]>old_d[nod]+cost)
                {
                    old_d[i]=old_d[nod]+cost;
                    from[i]=nod;
                    coada.push(i);
                }
            }
    }
}
bool flux()
{
    for(int i=0;i<=nodes;i++)
    {
        dist[i]=INF;
        real_d[i]=INF;
        from[i]=-1;
        use[i]=0;
    }
    dist[S]=0;
    real_d[S]=0;
    priority_queue<pii,vector<pii>, greater<pii>> coada;
    coada.push({0,S});
    while(!coada.empty())
    {
        int nod=coada.top().second;
        coada.pop();
        if(use[nod])
            continue;
        use[nod]=1;
        for(int i:muchii[nod])
            if(cap[nod][i]>0)
            {
                ll cost=0;
                if(nod==mns)
                {
                    if(i>=0&&i<n)
                        cost=-v[i][m-(k-cap[nod][i])-1];
                }
                if(nod==pls)
                {
                    if(i>=0&&i<n)
                        cost=v[i][k-cap[nod][i]];
                }
                if(nod>=0&&nod<n)
                {
                    if(i==mns)
                        cost=v[nod][m-cap[nod][i]];
                    if(i==pls)
                        cost=-v[nod][cap[nod][i]-1];
                }
                if(dist[i]>dist[nod]+cost+old_d[nod]-old_d[i])
                {
                    dist[i]=dist[nod]+cost+old_d[nod]-old_d[i];
                    real_d[i]=real_d[nod]+cost;
                    from[i]=nod;
                    coada.push({dist[i],i});
                }
            }
    }
    for(int i=0;i<=nodes;i++)
        old_d[i]=real_d[i];
    if(real_d[D]==INF)
        return 0;
    flow++;
    ans+=real_d[D];
    //cout<<flow<<' '<<ans<<'\n';
    for(int i=D;i!=S;i=from[i])
    {
        cap[from[i]][i]--;
        cap[i][from[i]]++;
    }
    return 1;
}
bool byplus(int a,int b)
{
    return cap[a][pls]>cap[b][pls];
}
long long find_maximum(int K, std::vector<std::vector<int>> vectoras)
{
    k=K;
	n = vectoras.size();
	m = vectoras[0].size();
	sol=vectoras;
    v=vectoras;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            sol[i][j]=-1;
    S=n;
    D=n+1;
    pls=n+2;
    mns=n+3;
    nodes=n+3;
    muchii[S].push_back(pls);
    muchii[pls].push_back(S);
    muchii[S].push_back(mns);
    muchii[mns].push_back(S);
    cap[S][pls]=k*n/2;
    cap[S][mns]=k*n/2;
    for(int i=0;i<n;i++)
    {
        muchii[pls].push_back(i);
        muchii[i].push_back(pls);
        cap[pls][i]=k;

        muchii[mns].push_back(i);
        muchii[i].push_back(mns);
        cap[mns][i]=k;

        muchii[i].push_back(D);
        muchii[D].push_back(i);
        cap[i][D]=k;
    }
    bellman();
    while(flux());
    ans=-ans;
    for(int i=0;i<n;i++)
    {
        l[i]=0;
        r[i]=m-1;
    }
    for(int i=0;i<n;i++)
        swap(cap[i][pls],cap[i][mns]);
    for(int pas=0;pas<k;pas++)
    {
        vector<int> linii;
        for(int i=0;i<n;i++)
            linii.push_back(i);
        sort(linii.begin(),linii.end(),byplus);
        for(int z=0;z<n;z++)
        {
            int i=linii[z];
            if(z<n/2)
            {
                assert(cap[i][pls]>0);
                cap[i][pls]--;
                sol[i][r[i]]=pas;
                r[i]--;
            }
            else
            {
                assert(cap[i][mns]>0);
                cap[i][mns]--;
                sol[i][l[i]]=pas;
                l[i]++;
            }
        }
    }
    allocate_tickets(sol);
	return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 12 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10