Submission #293111

#	Time	Username	Problem	Language	Result	Execution time	Memory
293111		shayan_p	Simurgh (IOI17_simurgh)	C++17	13 / 100	3075 ms	8488 KiB

simurgh

// Oh damn! Suddenly you're free to fly...

#include<bits/stdc++.h>
#include "simurgh.h"

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 510, maxM = 3e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

vector<pii> v[maxn];

set<int> TREE;
int h[maxn];
pii up[maxn];
bool mark[maxn];

int know[maxM];

int parid[maxn];

int ask(){
    vector<int> tmp;
    for(int x : TREE)
	tmp.PB(x);
    return count_common_roads(tmp);
}

template<int N> struct DSU{
    int pr[N];
    DSU(){
	memset(pr, -1, sizeof pr);
    }
    void clear(){
	memset(pr, -1, sizeof pr);
    }
    int fnd(int u){
	return pr[u] < 0 ? u : pr[u] = fnd(pr[u]);
    }
    bool mrg(int a, int b){
	if( (a = fnd(a)) == (b = fnd(b)) )
	    return 0;
	if(pr[a] > pr[b])
	    swap(a, b);
	pr[a]+= pr[b];
	pr[b] = a;
	return 1;
    }
    void mrg_know(int a, int b){
	a = fnd(a), b = fnd(b);	
	if(know[b] != -1)
	    assert(know[a] == know[b] || know[a] == -1), know[a] = know[b];
	else
	    know[b] = know[a];
    }
    void put_know(int a, int x){
	a = fnd(a);
	assert(know[a] == x || know[a] == -1);
	know[a] = x;
    }
};DSU<maxM> dsu;
    
void prep(int u, int par = -1){
    mark[u] = 1;
    h[u] = (par == -1 ? 0 : (h[par] + 1));
    up[u] = {h[u], -1};
    for(auto [y, c] : v[u]){
	if(!mark[y]){
	    parid[y] = c;
	    prep(y, u);
	    TREE.insert(c);
	    up[u] = min(up[u], up[y]);
	}
	else{
	    up[u] = min(up[u], (pii){h[y], c});
	}
    }    
}
void dfs(int u, int par = -1){
    if(up[u].F < h[u] - 1){
	TREE.insert(up[u].S);
	TREE.erase(parid[u]);
	int A = ask();
	TREE.insert(parid[u]);
	
	TREE.erase(parid[par]);
	int B = ask();
	TREE.insert(parid[par]);

	TREE.erase(up[u].S);
	
	if(A == B){
	    dsu.mrg_know(parid[u], parid[par]);
	    dsu.mrg(parid[u], parid[par]);	    
	}
	else if(A < B){
	    dsu.put_know(parid[u], 1);
	    dsu.put_know(parid[par], 0);
	}
	else{
	    dsu.put_know(parid[u], 0);
	    dsu.put_know(parid[par], 1);
	}
    }
    mark[u] = 1;
    for(auto [y, c] : v[u]){
	if(!mark[y])
	    dfs(y, u);
    }
}




bool bad_edge[maxM];

vector<int> wave;

void dfs2(int u){
    mark[u] = 1;
    for(auto [y, c] : v[u]){
	if(bad_edge[c] || mark[y])
	    continue;
	wave.PB(c);
	bad_edge[c] = 1;
	dfs2(y);
    }
}

DSU<maxn> dsu2;

vector<int> A, B;
int m;

int jungle(vector<int> vec){// TLE? // use DSU in this func
    dsu2.clear();
    TREE.clear();
    for(int id : vec)
	dsu2.mrg(A[id], B[id]), TREE.insert(id);
    int lz = 0;
    for(int i = 0; i < m; i++){
	if(know[i] != -1){
	    if(dsu2.mrg(A[i], B[i]))
		lz+= know[i], TREE.insert(i);
	}
    }
    return ask() - lz;
}

void solve(vector<int> ed){
    if(ed.empty())
	return;
    int x = jungle(ed);
    if(x == 0){
	for(int id : ed)
	    know[id] = 0;
	return;
    }
    if(x == sz(ed)){
	for(int id : ed)
	    know[id] = 1;
	return;
    }
    int mid = sz(ed) / 2;
    vector<int> v1, v2;
    for(int i = 0; i < sz(ed); i++){
	if(i < mid)
	    v1.PB(ed[i]);
	else
	    v2.PB(ed[i]);
    }
    solve(v1);
    solve(v2);
}

vector<int> find_roads(int n, vector<int> A, vector<int> B){
    ::A = A, ::B = B;
    m = sz(A);

    memset(know, -1, sizeof know);
    
    for(int i = 0; i < m; i++){
	v[A[i]].PB({B[i], i});
	v[B[i]].PB({A[i], i});
    }
    prep(0);
    memset(mark, 0, sizeof mark);
    dfs(0);

    for(int id : TREE){ /// yal boreshi!
	if(id == dsu.fnd(id)){
	    if(know[id] == -1)
		know[id] = 1;
	}
    }
    for(int id : TREE){
	know[id] = know[ dsu.fnd(id) ];
	assert(know[id] != -1);

	bad_edge[id] = 1;
    }
    
    while(true){
	memset(mark, 0, sizeof mark);
	wave.clear();
	for(int i = 0; i < n; i++){
	    if(!mark[i])
		dfs2(i);
	}
	if(wave.empty())
	    break;
	solve(wave);
    }
    
    vector<int> ret;
    for(int i = 0; i < m; i++){
	assert(know[i] != -1);
	if(know[i])
	    ret.PB(i);
    }
    assert(sz(ret) == n-1);
    return ret;
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30