| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1229269 | FIFI_cpp | 마상시합 토너먼트 (IOI12_tournament) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <fstream>
#include <iterator>
#include <set>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cctype>
#include <string>
#include <cassert>
#include <set>
#include <bitset>
#include <unordered_set>
#include <numeric>
#define all(a) a.begin(), a.end()
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define ppi pair<int,pair<int,int>>
#define int int64_t
using namespace std;
// /\_/\
// (= ._.)
// / > \>
// encouraging cat
const int INF = 10000000000000000;
//const int mod = 1000000007;
const int mod = 998244353;
const int MAXN = 200005;
//ifstream fin('xor.in');
//ofstream fout('xor.out');
vector<vector<int>> adj, adj_t;
int dp[MAXN];
struct Info {
int v;
bool type;
int index;
int random_pos;
};
void dfs(int node, int p)
{
int s = 0;
for (auto edge: adj[node])
{
if (edge == p)
{
continue;
}
dfs(edge, node);
s += dp[edge];
}
dp[node] = s + 1;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
int n = N;
int c = C;
int r = R;
adj.resize(c);
adj_t.resize(c);
for (int i = 0;i < n;i++)
{
if (K[i] < r)
{
K[i] = 0;
}
else
{
K[i] = 1;
}
}
for (int i = 0;i < c;i++)
{
E[i]--;
}
vector<Info> a(n);
for (int i = 0;i < n;i++)
{
a[i] = {K[i],false,i,-1};
}
vector<Info> info(c);
for (int i = 0;i < c;i++)
{
int mx = 0;
int random_pos = -1;
vector<int> edge;
for (int j = S[i];j <= E[i];j++)
{
mx = max(mx, a[i].v);
if (a[i].type && a[i].v == 0)
{
edge.pb(a[i].index);
}
else if (a[i].type == false)
{
random_pos = a[i].index;
}
}
if (mx == 0)
{
for (auto x: edge)
{
adj[x].pb(i);
}
}
info[i] = {mx, true, i, random_pos};
a.erase(a.begin() + S[i], a.begin() + E[i]);
a.insert(a.begin(), S[i], {mx, true, i, random_pos});
}
int res = 0;
for (int i = 0;i < c;i++)
{
if (adj_t[i].size() == 0 && info[i].v == 0)
{
dfs(i, -1);
res = max(res, dp[i]);
}
}
return 0;
}