Submission #652632

#	Time	Username	Problem	Language	Result	Execution time	Memory
652632		4EVER	Plahte (COCI17_plahte)	C++11	32 / 160	247 ms	32552 KiB

plahte

/******************************
*    author : @yayayaya       *
*    date : 21 / 10 / 2022    *
******************************/

/*   (≈ㅇᆽㅇ≈)♡    (≈ㅇᆽㅇ≈)♡    (≈ㅇᆽㅇ≈)♡    (≈ㅇᆽㅇ≈)♡    (≈ㅇᆽㅇ≈)♡ */
/*
                              /^--^\     /^--^\     /^--^\
                              \____/     \____/     \____/
                             /      \   /      \   /      \
                            |        | |        | |        |
                             \__  __/   \__  __/   \__  __/
        |^|^|^|^|^|^|^|^|^|^|^|^\ \^|^|^|^/ /^|^|^|^|^\ \^|^|^|^|^|^|^|^|^|^|^|^|
        | | | | | | | | | | | | |\ \| | |/ /| | | | | |\ \| | | | | | | | | | | |
        | | | | | | | | | | | | |/ /| | |\ \| | | | | |/ /| | | | | | | | | | | |
        | | | | | | | | | | | | |\/ | | | \/| | | | | |\/ | | | | | | | | | | | |
        #########################################################################
        | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
        | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |         */

/*******************************************************************************************
*            #################################################################             *
*            #                             _`                                #             *
*            #                          _ooOoo_                              #             *
*            #                         o8888888o                             #             *
*            #                         88" . "88                             #             *
*            #                         (| -_- |)                             #             *
*            #                         O\  =  /O                             #             *
*            #                      ____/`---'\____                          #             *
*            #                    .'  \|     |//  `.                         #             *
*            #                   /  \|||  :  |||//  \                        #             *
*            #                  /  _||||| -:- |||||_  \                      #             *
*            #                  |   | \  -  /'| |   |                        #             *
*            #                  | \_|  `\`---'//  |_/ |                      #             *
*            #                  \  .-\__ `-. -'__/-.  /                      #             *
*            #                ___`. .'  /--.--\  `. .'___                    #             *
*            #             ."" '<  `.___\_<|>_/___.' _> \"".                 #             *
*            #            | | :  `- \`. ;`. _/; .'/ /  .' ; |                #             *
*            #            \  \ `-.   \_\_`. _.'_/_/  -' _.' /                #             *
*            #=============`-.`___`-.__\ \___  /__.-'_.'_.-'=================#             *
*                                      `=--=-'                                             *
*                                                                                          *
*                                       /\_/\*                                             *
*                                      (  -.-)                                             *
*         _.-/`)                       / >O  \>1                            _.-/`)         *
*        // / / )                                                         // / / )         *
*     .=// / / / )              /\_/\           /\_/\                  .=// / / / )        *
*    //`/ / / / /              (  -.-)         (  -.-)                //`/ / / / /         *
*   // /     ` /               / >O  \>1       / >O  \>1             // /     ` /          *
*   \       /                                                        \       /             *
*    ))    .'            /\_/\         /\_/\         /\_/\            ))    .'             *
*   //    /             (  -.-)       (  -.-)       (  -.-)           //    /              *
*        /              / >O  \>1     / >O  \>1     / >O  \>1              /               *
*                                                                                          *
*******************************************************************************************/

#include <bits/stdc++.h>
// #pragma GCC optimize("O2")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimize ("O3,unroll-loops,no-stack-protector")
// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define PB push_back
#define ALL(i_) i_.begin(), i_.end()
#define LOG2(x) (31 - __builtin_clz(x))
#define getBit(x, i) ((x >> i) & 1)
#define rd(l, r) (l + rng() % (r - l + 1))
#define FOR(i_, a_, b_)  for(int i_ = (int) (a_); i_ <= (int) (b_); ++i_)
#define FORD(i_, a_, b_) for(int i_ = (int) (a_); i_ >= (int) (b_); --i_)
#define db(val) "["#val" = "<<(val)<<"] "

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;

template<class X, class Y> bool minimize(X &x, const Y &y){
    X eps = 1e-9;
    if (x > y + eps) {
        x = y;
        return 1;
    }
    return 0;
}

template<class X, class Y> bool maximize(X &x, const Y &y) {
    X eps = 1e-9;
    if (x + eps < y) {
        x = y;
        return 1;
    }
    return 0;
}

template<class T> T Abs(const T &x) { return (x < 0 ? -x : x); }

const int mod = (int) 1e9 + 7;
const int oo = (int) 1e9 + 99;
const int LOG = (int) 20;
const ii dxy8[] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1}, {1, -1}, {1, 1}, {-1, 1}, {-1, -1} };
const ii dxy4[] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };

const int maxn = (int) 1e5 + 1;

int n, m;
vector<array<int, 3>> event;
vector<int> X1, X2, X3, color, par, res;
set<array<int, 3>> se;
vector<set<int>> co;
vector<vector<int>> adj;

int getPar(int pos){
	array<int, 3> cur = {pos, 0, 0};
	auto it = se.lower_bound(cur);
	if(it == se.end()) return 0;
	if((*it)[1] == -1) return par[(*it)[2]];
	return (*it)[2];
}

int cnt;
vector<int> toNode, tin, tout;

void getSize(int u = 0, int par = -1){	
	toNode[++cnt] = u;
	tin[u] = cnt;
	for(int v : adj[u]) if(v != par) getSize(v, u);
	tout[u] = cnt;
}

set<int> cur;

#define sz(x) (tout[x] - tin[x] + 1)

void DFS(int u = 0, int par = -1, bool isClear = 0){
	int bigChild = -1;
	for(int v : adj[u]) if(v != par){
		if((bigChild == -1) || (sz(v) > sz(bigChild))) bigChild = v;
	}
	for(int v : adj[u]) if(v != par && v != bigChild) DFS(v, u, 1);
	if(bigChild != -1) DFS(bigChild, u, 0);
	for(int v : adj[u]) if(v != par && v != bigChild){
		for(int p = tin[v]; p <= tout[v]; p++){
			int x = toNode[p];
			for(auto c : co[x]) cur.insert(c);
		}
	}
	for(auto c : co[u]) cur.insert(c);
	res[u] = (int) cur.size();
	if(isClear){
		cur.clear();
	}
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define TASK "PLAHTE"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    cin >> n >> m;

    X1.resize(n + 1, 0);
    X2.resize(n + 1, 0);

    FOR(i, 1, n){
    	int x1, x2; cin >> x1 >> X1[i] >> x2 >> X2[i];
    	event.PB({x1, -1, i});
    	event.PB({x2,  1, i});
    }

    X3.resize(m + 1, 0);
    color.resize(m + 1, 0);
    FOR(i, 1, m){
    	int x; 
    	cin >> x >> X3[i] >> color[i];
    	event.PB({x, 0, i});
    }

    sort(ALL(event));

    par.resize(n + 1, 0);
    co.resize(n + 1, {});
    for(auto x : event){
    	if(x[1] == -1){
    		par[x[2]] = getPar(X1[x[2]]);
    		se.insert({X1[x[2]], -1, x[2]});
    		se.insert({X2[x[2]],  1, x[2]});
    	}
    	else if(x[1] == 0){
    		co[getPar(X3[x[2]])].insert(color[x[2]]);
    	}
    	else{
    		se.erase({X1[x[2]], -1, x[2]});
    		se.erase({X2[x[2]],  1, x[2]});
    	}
    }

    adj.resize(n + 1);

    FOR(i, 1, n){
    	adj[i].PB(par[i]);
    	adj[par[i]].PB(i);
    }

    res.resize(n + 1, 0);
    toNode.resize(n + 1, 0);
    tin.resize(n + 1, 0);
    tout.resize(n + 1, 0);

    getSize();
    DFS();

    FOR(i, 1, n) cout << res[i] << "\n";
    return 0;
}

/// CONCACOCONCACOCONCACOCONCACOCONCACOCONCACOCONCACOCONCACOCONCACO /// 

Compilation message (stderr)

plahte.cpp: In function 'int main()':
plahte.cpp:159:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:160:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 32
• Subtask 2: 0 / 32
• Subtask 3: 32 / 32
• Subtask 4: 0 / 32
• Subtask 5: 0 / 32