oj.uz

Submission #293579

# Submission time Handle Problem Language Result Execution time Memory
293579 2020-09-08T08:18:13 Z shayan_p Simurgh (IOI17_simurgh) C++17
32 / 100
 907 ms 8328 KB 
// 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)
	    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 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);
    memset(mark, 0, sizeof mark);
    tree_ask = ask();
    dfs(0);

    for(int i : TREE)
	dfs_tree.PB(i);
    
    int TOT = 0;

    for(int id : TREE){
	if(id == dsu.fnd(id) && know[id] == -1){
	    know[id] = 0;
	}
    }
    for(int id : TREE){
	know[id] = know[ dsu.fnd(id) ];
	ASSERT(know[id] != -1, 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;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB correct
2 Correct 2 ms 2688 KB correct
3 Correct 2 ms 2688 KB correct
4 Correct 2 ms 2688 KB correct
5 Correct 2 ms 2688 KB correct
6 Correct 2 ms 2688 KB correct
7 Correct 2 ms 2688 KB correct
8 Correct 2 ms 2688 KB correct
9 Correct 2 ms 2688 KB correct
10 Correct 2 ms 2688 KB correct
11 Correct 2 ms 2688 KB correct
12 Correct 2 ms 2688 KB correct
13 Correct 2 ms 2688 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB correct
2 Correct 2 ms 2688 KB correct
3 Correct 2 ms 2688 KB correct
4 Correct 2 ms 2688 KB correct
5 Correct 2 ms 2688 KB correct
6 Correct 2 ms 2688 KB correct
7 Correct 2 ms 2688 KB correct
8 Correct 2 ms 2688 KB correct
9 Correct 2 ms 2688 KB correct
10 Correct 2 ms 2688 KB correct
11 Correct 2 ms 2688 KB correct
12 Correct 2 ms 2688 KB correct
13 Correct 2 ms 2688 KB correct
14 Correct 8 ms 2688 KB correct
15 Correct 6 ms 2816 KB correct
16 Correct 5 ms 2688 KB correct
17 Correct 6 ms 2688 KB correct
18 Correct 4 ms 2688 KB correct
19 Correct 6 ms 2688 KB correct
20 Correct 6 ms 2688 KB correct
21 Correct 6 ms 2688 KB correct
22 Correct 3 ms 2688 KB correct
23 Correct 3 ms 2688 KB correct
24 Correct 3 ms 2688 KB correct
25 Correct 2 ms 2688 KB correct
26 Runtime error 2 ms 2688 KB Execution failed because the return code was nonzero
27 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB correct
2 Correct 2 ms 2688 KB correct
3 Correct 2 ms 2688 KB correct
4 Correct 2 ms 2688 KB correct
5 Correct 2 ms 2688 KB correct
6 Correct 2 ms 2688 KB correct
7 Correct 2 ms 2688 KB correct
8 Correct 2 ms 2688 KB correct
9 Correct 2 ms 2688 KB correct
10 Correct 2 ms 2688 KB correct
11 Correct 2 ms 2688 KB correct
12 Correct 2 ms 2688 KB correct
13 Correct 2 ms 2688 KB correct
14 Correct 8 ms 2688 KB correct
15 Correct 6 ms 2816 KB correct
16 Correct 5 ms 2688 KB correct
17 Correct 6 ms 2688 KB correct
18 Correct 4 ms 2688 KB correct
19 Correct 6 ms 2688 KB correct
20 Correct 6 ms 2688 KB correct
21 Correct 6 ms 2688 KB correct
22 Correct 3 ms 2688 KB correct
23 Correct 3 ms 2688 KB correct
24 Correct 3 ms 2688 KB correct
25 Correct 2 ms 2688 KB correct
26 Runtime error 2 ms 2688 KB Execution failed because the return code was nonzero
27 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB correct
2 Correct 2 ms 2688 KB correct
3 Correct 547 ms 6648 KB correct
4 Correct 875 ms 8312 KB correct
5 Correct 880 ms 8184 KB correct
6 Correct 645 ms 8184 KB correct
7 Correct 649 ms 8072 KB correct
8 Correct 638 ms 8056 KB correct
9 Correct 887 ms 8328 KB correct
10 Correct 878 ms 8184 KB correct
11 Correct 878 ms 8056 KB correct
12 Correct 907 ms 8056 KB correct
13 Correct 2 ms 2688 KB correct
14 Correct 872 ms 8056 KB correct
15 Correct 886 ms 8184 KB correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB correct
2 Correct 2 ms 2688 KB correct
3 Correct 2 ms 2688 KB correct
4 Correct 2 ms 2688 KB correct
5 Correct 2 ms 2688 KB correct
6 Correct 2 ms 2688 KB correct
7 Correct 2 ms 2688 KB correct
8 Correct 2 ms 2688 KB correct
9 Correct 2 ms 2688 KB correct
10 Correct 2 ms 2688 KB correct
11 Correct 2 ms 2688 KB correct
12 Correct 2 ms 2688 KB correct
13 Correct 2 ms 2688 KB correct
14 Correct 8 ms 2688 KB correct
15 Correct 6 ms 2816 KB correct
16 Correct 5 ms 2688 KB correct
17 Correct 6 ms 2688 KB correct
18 Correct 4 ms 2688 KB correct
19 Correct 6 ms 2688 KB correct
20 Correct 6 ms 2688 KB correct
21 Correct 6 ms 2688 KB correct
22 Correct 3 ms 2688 KB correct
23 Correct 3 ms 2688 KB correct
24 Correct 3 ms 2688 KB correct
25 Correct 2 ms 2688 KB correct
26 Runtime error 2 ms 2688 KB Execution failed because the return code was nonzero
27 Halted 0 ms 0 KB -