oj.uz

답안 #864838

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
864838 2023-10-23T16:52:05 Z andrei_boaca 카니발 티켓 (IOI20_tickets) C++17
39 / 100
 3000 ms 101516 KB 
#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.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 14 ms 6792 KB Output is correct
6 Correct 382 ms 25692 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2548 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 4 ms 2644 KB Output is correct
5 Correct 30 ms 9812 KB Output is correct
6 Correct 790 ms 101516 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2544 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 18 ms 2656 KB Output is correct
5 Correct 981 ms 9108 KB Output is correct
6 Execution timed out 3019 ms 65112 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 67 ms 2736 KB Output is correct
5 Execution timed out 3016 ms 8792 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 3 ms 2648 KB Output is correct
3 Correct 8 ms 2652 KB Output is correct
4 Correct 19 ms 2612 KB Output is correct
5 Correct 35 ms 2648 KB Output is correct
6 Correct 52 ms 2648 KB Output is correct
7 Correct 2 ms 2392 KB Output is correct
8 Correct 9 ms 2396 KB Output is correct
9 Correct 50 ms 2704 KB Output is correct
10 Correct 43 ms 2652 KB Output is correct
11 Correct 68 ms 2652 KB Output is correct
12 Correct 58 ms 2720 KB Output is correct

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 3 ms 2648 KB Output is correct
3 Correct 8 ms 2652 KB Output is correct
4 Correct 19 ms 2612 KB Output is correct
5 Correct 35 ms 2648 KB Output is correct
6 Correct 52 ms 2648 KB Output is correct
7 Correct 2 ms 2392 KB Output is correct
8 Correct 9 ms 2396 KB Output is correct
9 Correct 50 ms 2704 KB Output is correct
10 Correct 43 ms 2652 KB Output is correct
11 Correct 68 ms 2652 KB Output is correct
12 Correct 58 ms 2720 KB Output is correct
13 Correct 63 ms 9812 KB Output is correct
14 Correct 178 ms 9812 KB Output is correct
15 Correct 2292 ms 10012 KB Output is correct
16 Execution timed out 3063 ms 8796 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 14 ms 6792 KB Output is correct
6 Correct 382 ms 25692 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2548 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 4 ms 2644 KB Output is correct
11 Correct 30 ms 9812 KB Output is correct
12 Correct 790 ms 101516 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2544 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 18 ms 2656 KB Output is correct
17 Correct 981 ms 9108 KB Output is correct
18 Execution timed out 3019 ms 65112 KB Time limit exceeded
19 Halted 0 ms 0 KB -