oj.uz

Submission #372383

# Submission time Handle Problem Language Result Execution time Memory
372383 2021-02-28T00:26:49 Z arwaeystoamneg Teams (IOI15_teams) C++17
34 / 100
 4000 ms 10700 KB 
#include "teams.h"
/*
ID: awesome35
LANG: C++14
TASK: vans
*/
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
//const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353
const ld pi = 3.1415926535;

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "ioi")
			freopen((s + ".out").c_str(), "w", stdout);
	}
}
template <int MAXV, class T = int> struct Dinic {
	const static bool SCALING = false; // non-scaling = V^2E, Scaling=VElog(U) with higher constant
	int lim = 1;
	const T INF = numeric_limits<T>::max();
	struct edge {
		int to, rev;
		T cap, flow;
	};
	int s = 0, t = MAXV - 1;

	int level[MAXV], ptr[MAXV];
	vector<edge> adj[MAXV];
	void addEdge(int a, int b, T cap, bool isDirected = true) {
		adj[a].push_back({ b, sz(adj[b]), cap, 0 });
		adj[b].push_back({ a, sz(adj[a]) - 1, isDirected ? 0 : cap, 0 });
	}
	bool bfs() {
		queue<int> q({ s });
		fill(level, level + MAXV, -1);
		level[s] = 0;
		while (!q.empty() && level[t] == -1) {
			int v = q.front();
			q.pop();
			for (auto e : adj[v]) {
				if (level[e.to] == -1 && e.flow < e.cap && (!SCALING || e.cap - e.flow >= lim)) {
					q.push(e.to);
					level[e.to] = level[v] + 1;
				}
			}
		}
		return level[t] != -1;
	}
	T dfs(int v, T flow) {
		if (v == t || !flow)
			return flow;
		for (; ptr[v] < adj[v].size(); ptr[v]++) {
			edge& e = adj[v][ptr[v]];
			if (level[e.to] != level[v] + 1)
				continue;
			if (T pushed = dfs(e.to, min(flow, e.cap - e.flow))) {
				e.flow += pushed;
				adj[e.to][e.rev].flow -= pushed;
				return pushed;
			}
		}
		return 0;
	}
	long long calc() {
		long long flow = 0;
		for (lim = SCALING ? (1 << 30) : 1; lim > 0; lim >>= 1) {
			while (bfs()) {
				fill(ptr, ptr + MAXV, 0);
				while (T pushed = dfs(s, INF))
					flow += pushed;
			}
		}
		return flow;
	}
};
const int MAX = 100;
int n, m;
vi a, b, k;
void init(int A, int* B, int* c)
{
	n = A;
	a.rsz(n);
	b.rsz(n);
	F0R(i, n)a[i] = B[i], a[i]--;
	F0R(i, n)b[i] = c[i], b[i]--;
}
bool sub1()
{
	Dinic<MAX * 2 + 2> g;
	F0R(i, n)g.addEdge(0, i + 1, 1);
	int sum = 0;
	vi count(MAX);
	trav(x, k)
	{
		sum += x + 1;
		count[x]++;
	}
	F0R(i, n)
	{
		FOR(j, a[i], b[i] + 1)g.addEdge(i + 1, MAX + 1 + j, 1);
	}
	F0R(i, MAX)g.addEdge(MAX + 1 + i, MAX * 2 + 1, count[i] * (i + 1));
	return g.calc() == sum;
}
bool sub2()
{
	vi order(n);
	iota(all(order), 0);
	sort(all(order), [](int i, int j) {return a[i] < a[j]; });
	sort(all(k));
	priority_queue<int, vi, greater<int>>todo;
	int i = 0, j = 0;
	while (i != n && j != m)
	{
		while (i != n && a[order[i]] <= k[j])todo.push(b[order[i++]]);
		F0R(t, k[j] + 1)
		{
			while (sz(todo))
			{
				if (todo.top() < k[j])todo.pop();
				else break;
			}
			if (sz(todo) == 0)return 0;
			todo.pop();
		}
		j++;
	}
	return 1;
}
int can(int A, int* B)
{
	m = A;
	k.rsz(m);
	F0R(i, m)k[i] = B[i], k[i]--;
	if (n <= 100)
	{
		return sub1();
	}
	else
	{
		return sub2();
	}
}

Compilation message

teams.cpp: In instantiation of 'T Dinic<MAXV, T>::dfs(int, T) [with int MAXV = 202; T = int]':
teams.cpp:111:23:   required from 'long long int Dinic<MAXV, T>::calc() [with int MAXV = 202; T = int]'
teams.cpp:145:16:   required from here
teams.cpp:94:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Dinic<202>::edge, std::allocator<Dinic<202>::edge> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   for (; ptr[v] < adj[v].size(); ptr[v]++) {
teams.cpp: In function 'void setIO(std::string)':
teams.cpp:54:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   54 |   freopen((s + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:56:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   56 |    freopen((s + ".out").c_str(), "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 25 ms 492 KB Output is correct
4 Correct 26 ms 492 KB Output is correct
5 Correct 26 ms 492 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 4 ms 364 KB Output is correct
8 Correct 4 ms 364 KB Output is correct
9 Correct 4 ms 364 KB Output is correct
10 Correct 4 ms 364 KB Output is correct
11 Correct 1 ms 748 KB Output is correct
12 Correct 6 ms 364 KB Output is correct
13 Correct 9 ms 364 KB Output is correct
14 Correct 14 ms 364 KB Output is correct
15 Correct 23 ms 492 KB Output is correct
16 Correct 45 ms 740 KB Output is correct
17 Correct 2 ms 364 KB Output is correct
18 Correct 2 ms 364 KB Output is correct
19 Correct 2 ms 364 KB Output is correct
20 Correct 2 ms 364 KB Output is correct
21 Correct 2 ms 364 KB Output is correct
22 Correct 2 ms 364 KB Output is correct
23 Correct 2 ms 364 KB Output is correct
24 Correct 3 ms 364 KB Output is correct
25 Correct 3 ms 364 KB Output is correct
26 Correct 3 ms 364 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2284 KB Output is correct
2 Correct 17 ms 2284 KB Output is correct
3 Correct 30 ms 2920 KB Output is correct
4 Correct 20 ms 3180 KB Output is correct
5 Correct 14 ms 2284 KB Output is correct
6 Correct 15 ms 2284 KB Output is correct
7 Correct 11 ms 2284 KB Output is correct
8 Correct 11 ms 2284 KB Output is correct
9 Correct 8 ms 3176 KB Output is correct
10 Correct 10 ms 3048 KB Output is correct
11 Correct 10 ms 2920 KB Output is correct
12 Correct 11 ms 2920 KB Output is correct
13 Correct 18 ms 2668 KB Output is correct
14 Correct 20 ms 2920 KB Output is correct
15 Correct 17 ms 2412 KB Output is correct
16 Correct 18 ms 3436 KB Output is correct
17 Correct 16 ms 3564 KB Output is correct
18 Correct 17 ms 3692 KB Output is correct

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2323 ms 2684 KB Output is correct
2 Correct 2746 ms 3140 KB Output is correct
3 Execution timed out 4081 ms 3768 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4089 ms 10700 KB Time limit exceeded
2 Halted 0 ms 0 KB -