Submission #117502

#	Time	Username	Problem	Language	Result	Execution time	Memory
117502		zubec	Teams (IOI15_teams)	C++14	21 / 100	1588 ms	524288 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 500100;

vector <int> g[N];

pair<int, int> a[N];

int n;

void init(int N, int A[], int B[]) {
    n = N;
    for (int i = 1; i <= n; i++){
        a[i] = {A[i-1], B[i-1]};
    }
}

bool used[N];
int mt[N];

int try_khun(int v){
    if (used[v])
        return 0;
    used[v] = 1;
    for (int i = 0; i < g[v].size(); i++){
        int to = g[v][i];
        if (mt[to] == -1 || try_khun(mt[to])){
            mt[to] = v;
            return 1;
        }
    }
    return 0;
}

int can(int M, int K[]) {
    ll sum = 0;
    for (int i = 1; i <= M; i++){
        sum += K[i-1];
    }
    if (sum > n)
        return 0;
    for (int i = 1; i <= n+sum; i++){
        g[i].clear();
        mt[i] = -1;
    }
    int kol = n;
    for (int i = 1; i <= M; i++){
        for (int j = 1; j <= n; j++){
            if (a[j].first <= K[i-1] && K[i-1] <= a[j].second){
                for (int l = 1; l <= K[i-1]; l++){
                    g[j].push_back(kol+l);
                    g[kol+l].push_back(j);
                }
            }
        }
        kol += K[i-1];
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n+sum; j++)
            used[j] = 0;
        try_khun(i);
    }
    for (int i = n+1; i <= n+sum; i++){
        if (mt[i] == -1)
            return 0;
    }
    return 1;

}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:14:34: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 void init(int N, int A[], int B[]) {
                                  ^
teams.cpp:6:11: note: shadowed declaration is here
 const int N = 500100;
           ^
teams.cpp: In function 'int try_khun(int)':
teams.cpp:28:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++){
                     ~~^~~~~~~~~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23