Submission #862663

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
862663	2023-10-18 18:32:49	mraron	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1323 ms	467684 KiB

bitaro

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100001;
int n,m,q;
vector<int> adj[MAXN];
vector<int> badj[MAXN];
const int blksz=344;
vector<pair<int,int>> best[MAXN];
int vis[MAXN], indeg[MAXN], volt[MAXN];
int currMark=0;
void dfs(int x) {
    vis[x]=1;
    for(auto& i:best[x]) i.first++;
    best[x].push_back({0, x});
    if(best[x].size()>blksz) best[x].resize(blksz);
    
    for(int i:adj[x]) {
        indeg[i]--;
        
        vector<pair<int,int>> res;
        res.resize(best[x].size()+best[i].size());
        merge(best[i].begin(), best[i].end(), best[x].begin(), best[x].end(), res.begin(), [&](auto& x, auto& y) -> bool {
            return x>y;
        });
        best[i].clear();
        best[i].shrink_to_fit();
        
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86