Submission #293647

#	Time	Username	Problem	Language	Result	Execution time	Memory
293647		shayan_p	Simurgh (IOI17_simurgh)	C++17	70 / 100	1120 ms	9048 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], par[maxn];

int ASKED = 0;

int ask(){
    //    assert(++ASKED <= 10000);//////////////    
    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)
	    know[a] = know[b];
	else
	    know[b] = know[a];
    }
    void put_know(int a, int x){
	a = fnd(a);
	know[a] = x;
    }
};DSU<maxM> dsu;

void prep(int u, int pr = -1){
    par[u] = pr;
    mark[u] = 1;
    h[u] = (pr == -1 ? 0 : (h[pr] + 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 if(y != pr){
	    up[u] = min(up[u], (pii){h[y], c});
	}
    }    
}

int tree_ask;
vector<int> A, B;
int n, m;

void check(int in, int out){
    TREE.insert(out);
    TREE.erase(in);
    int x = ask();
    if(x == tree_ask){
	dsu.mrg_know(in, out);
	dsu.mrg(in, out);	    
    }
    if(x < tree_ask){
	dsu.put_know(in, 1);
	dsu.put_know(out, 0);
    }
    if(x > tree_ask){
	dsu.put_know(in, 0);
	dsu.put_know(out, 1);
    }
    TREE.insert(in);
    TREE.erase(out);
}

bool mark_calc[maxn];

void dfs(int u){
    if(par[u] != -1 && up[u].F == h[u]){
	dsu.put_know(parid[u], 1);
    }
    mark[u] = 1;

    pair<int, pii> mnh = {h[u], {-1, -1}};
    for(auto [y, c] : v[u]){
	mnh = min(mnh, (pair<int, pii>){h[y], {y, c}});
    }
    if(mnh.F < h[u] - 1){	
	int tmp = u;
	while(tmp != mnh.S.F && !mark_calc[tmp]){
	    mark_calc[tmp] = 1;
	    check(parid[tmp], mnh.S.S);
	    tmp = par[tmp];
	}
	if(tmp != mnh.S.F){
	    check(parid[tmp], mnh.S.S);
	}
	if(know[ dsu.fnd(parid[u]) ] == -1){
	    dsu.put_know(parid[u], 0);
	}
    }
    for(auto [y, c] : v[u]){
	if(!mark[y])
	    dfs(y);
    }
}




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> dfs_tree;

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

void solve(vector<int> ed){
    if(ed.empty())
	return;
    int x = jungle(ed);
    //    assert(x >= 0 && x <= sz(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);
}

void ASSERT(bool x, int sig){
    if(!x)
	exit(sig);
}

vector<int> find_roads(int n, vector<int> A, vector<int> B){
    ::A = A, ::B = B, ::n = n;
    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);
    tree_ask = ask();
    for(int id = 0; id < m; id++){
	if(abs(h[A[id]] - h[B[id]]) > 1){
	    if(h[A[id]] < h[B[id]])
		swap(A[id], B[id]);
	    int tmp = A[id];
	    
	    int ONE = -1;
	    while(tmp != B[id]){
		if(know[ dsu.fnd(parid[tmp]) ] == -1){
		    check(parid[tmp], id);
		}
		else{
		    ONE = parid[tmp];
		}
		tmp = par[tmp];
	    }

	    bool is = 0;
	    tmp = A[id];
	    while(tmp != B[id]){
		if(know[ dsu.fnd(parid[tmp]) ] == -1){
		    is = 1;
		}
		tmp = par[tmp];
	    }

	    if(is){
		if(ONE != -1)
		    check(ONE, id);
		tmp = A[id];
		if(know[ dsu.fnd(id) ] == -1)
		    dsu.put_know(id, 0);
	    }
	}	    
    }
    for(int i : TREE){
	if(know[ dsu.fnd(i) ] == -1)// boreshi
	    dsu.put_know(i, 1);
    }
    
    for(int i : TREE)
	dfs_tree.PB(i);
    
    int TOT = 0;

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

	bad_edge[id] = 1;

	TOT+= know[id];
    }
    
    // assert(TOT == ask());
    //    ASSERT(TOT == tree_ask, 1);
    
    int ROUND = 0;
    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);
	//	ASSERT(sz(wave) < n, 2);
	//	ASSERT(++ROUND <= n, 3);
    }
    
    vector<int> ret;
    for(int i = 0; i < m; i++){
	//	ASSERT(know[i] != -1, 4);
	if(know[i])
	    ret.PB(i);
    }
    //    ASSERT(sz(ret) == n-1, 5);
    return ret;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:287:9: warning: unused variable 'ROUND' [-Wunused-variable]
  287 |     int ROUND = 0;
      |         ^~~~~

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