oj.uz

Submission #49984

# Submission time Handle Problem Language Result Execution time Memory
49984 2018-06-05T23:05:38 Z Benq Simurgh (IOI17_simurgh) C++14
51 / 100
 153 ms 7288 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

#include "simurgh.h"

vpi adj[500];
int comp[500];
vi tre[500], tmp[500], allComp;
int n;
int need[500*499/2], sec[500*499/2];
vi u,v, res;

template<int SZ> struct DSU {
    int par[SZ], sz[SZ];
    DSU() {
        F0R(i,SZ) par[i] = i, sz[i] = 1;
    }
    
    int get(int x) { // path compression
    	if (par[x] != x) par[x] = get(par[x]);
    	return par[x];
    }
    
    bool unite(int x, int y) { // union-by-rank
    	x = get(x), y = get(y);
    	if (x == y) return 0;
    	if (sz[x] < sz[y]) swap(x,y);
    	sz[x] += sz[y], par[y] = x;
    	return 1;
    }
};

int co = 0;

/*int count_common_roads(vi z) {
    co ++;
    assert(sz(z) == n-1);
    DSU<500> D = DSU<500>();
    int ret = 0;
    for (int i: z) {
        if (!D.unite(u[i],v[i])) exit(5);
        if (sec[i]) ret ++;
    }
    return ret;
}*/

void test(int ind) {
    vpi bes;
    
    for (int x: tmp[ind]) {
        vi z = {x};
        for (int i: allComp) {
            if (i != ind && i > 0) z.pb(tmp[i].back());
            z.insert(z.end(),all(tre[i]));
        }
        bes.pb({count_common_roads(z),x});
    }
    
    sort(all(bes));
    for (auto a: bes) {
        if (a.f == bes.back().f) {
            // cout << "ZZ " << a.s << " " << sz(bes) << "\n";
            need[a.s] = 1;
            res.pb(a.s);
        } else need[a.s] = -1;
    }
}

void dfs(int x, int lab) {
    comp[x] = lab;
    for (auto a: adj[x]) if (comp[a.f] == -1) {
        tre[lab].pb(a.s);
        dfs(a.f,lab);
    }
}

void test() {
    res.clear();
    FOR(i,1,n) {
        tre[i].clear();
        tmp[i].clear();
    }
    
    allComp.clear();
    allComp.pb(0);
    
    F0R(i,n) if (comp[i] == -1) {
        allComp.pb(i);
        dfs(i,i);
    }
    
    F0R(i,n) if (comp[i] != 0) 
        for (auto a: adj[i]) if (need[a.s] == 0 && comp[a.f] == 0) {
            //cout << "HUH " << i << " " << a.f << " " << a.s << "\n";
            tmp[comp[i]].pb(a.s);
        }
    
    for (int i: allComp) if (i) test(i);
    for (int i: res) tre[0].pb(i);
}

vector<int> find_roads(int N, vi U, vi V) {
    n = N, u = U, v = V;
    
   // for (int i: v) cout << i << " ";
    //cout << ""
    F0R(i,sz(u)) {
        adj[u[i]].pb({v[i],i});
        adj[v[i]].pb({u[i],i});
        //cout << "OH " << u[i] << " " << v[i] << " " << i << "\n";
    }
    
    FOR(i,1,n) comp[i] = -1;
    while (1) {
        for (int i: tre[0]) comp[u[i]] = comp[v[i]] = 0;
        
        int lef = 0;
        F0R(i,n) if (comp[i] != 0) {
            comp[i] = -1;
            lef ++;
        }
        
        if (lef == 0) break;
        test();
    }
    
    vi ans;
    F0R(i,sz(u)) if (need[i] == 1) ans.pb(i);
    // cout << co << "\n";
    return ans;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB correct
2 Correct 2 ms 484 KB correct
3 Correct 2 ms 484 KB correct
4 Correct 2 ms 484 KB correct
5 Correct 2 ms 668 KB correct
6 Correct 2 ms 668 KB correct
7 Correct 2 ms 668 KB correct
8 Correct 2 ms 668 KB correct
9 Correct 2 ms 668 KB correct
10 Correct 2 ms 668 KB correct
11 Correct 2 ms 668 KB correct
12 Correct 2 ms 668 KB correct
13 Correct 2 ms 668 KB correct
14 Correct 3 ms 668 KB correct
15 Correct 2 ms 668 KB correct
16 Correct 2 ms 668 KB correct
17 Correct 4 ms 668 KB correct
18 Correct 2 ms 668 KB correct
19 Correct 4 ms 668 KB correct
20 Correct 4 ms 668 KB correct
21 Correct 4 ms 668 KB correct
22 Correct 3 ms 668 KB correct
23 Correct 3 ms 668 KB correct
24 Correct 2 ms 696 KB correct
25 Correct 3 ms 696 KB correct
26 Correct 3 ms 696 KB correct
27 Correct 3 ms 696 KB correct
28 Correct 3 ms 696 KB correct
29 Correct 2 ms 696 KB correct
30 Correct 3 ms 696 KB correct
31 Correct 4 ms 696 KB correct
32 Correct 3 ms 700 KB correct
33 Correct 3 ms 700 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB correct
2 Correct 2 ms 484 KB correct
3 Correct 2 ms 484 KB correct
4 Correct 2 ms 484 KB correct
5 Correct 2 ms 668 KB correct
6 Correct 2 ms 668 KB correct
7 Correct 2 ms 668 KB correct
8 Correct 2 ms 668 KB correct
9 Correct 2 ms 668 KB correct
10 Correct 2 ms 668 KB correct
11 Correct 2 ms 668 KB correct
12 Correct 2 ms 668 KB correct
13 Correct 2 ms 668 KB correct
14 Correct 3 ms 668 KB correct
15 Correct 2 ms 668 KB correct
16 Correct 2 ms 668 KB correct
17 Correct 4 ms 668 KB correct
18 Correct 2 ms 668 KB correct
19 Correct 4 ms 668 KB correct
20 Correct 4 ms 668 KB correct
21 Correct 4 ms 668 KB correct
22 Correct 3 ms 668 KB correct
23 Correct 3 ms 668 KB correct
24 Correct 2 ms 696 KB correct
25 Correct 3 ms 696 KB correct
26 Correct 3 ms 696 KB correct
27 Correct 3 ms 696 KB correct
28 Correct 3 ms 696 KB correct
29 Correct 2 ms 696 KB correct
30 Correct 3 ms 696 KB correct
31 Correct 4 ms 696 KB correct
32 Correct 3 ms 700 KB correct
33 Correct 3 ms 700 KB correct
34 Correct 96 ms 2044 KB correct
35 Correct 104 ms 2300 KB correct
36 Correct 63 ms 2300 KB correct
37 Correct 7 ms 2300 KB correct
38 Correct 153 ms 2644 KB correct
39 Correct 53 ms 2928 KB correct
40 Correct 67 ms 2928 KB correct
41 Correct 13 ms 3136 KB correct
42 Correct 12 ms 3368 KB correct
43 Correct 56 ms 3368 KB correct
44 Correct 56 ms 3368 KB correct
45 Correct 55 ms 3368 KB correct
46 Correct 42 ms 3368 KB correct
47 Correct 21 ms 3368 KB correct
48 Correct 4 ms 3368 KB correct
49 Correct 12 ms 3368 KB correct
50 Correct 24 ms 3368 KB correct
51 Correct 78 ms 3368 KB correct
52 Correct 53 ms 3368 KB correct
53 Correct 40 ms 3368 KB correct
54 Correct 62 ms 3800 KB correct
55 Correct 64 ms 3904 KB correct
56 Correct 51 ms 3904 KB correct
57 Correct 54 ms 3904 KB correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3904 KB correct
2 Correct 2 ms 3904 KB correct
3 Incorrect 81 ms 7288 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB correct
2 Correct 2 ms 484 KB correct
3 Correct 2 ms 484 KB correct
4 Correct 2 ms 484 KB correct
5 Correct 2 ms 668 KB correct
6 Correct 2 ms 668 KB correct
7 Correct 2 ms 668 KB correct
8 Correct 2 ms 668 KB correct
9 Correct 2 ms 668 KB correct
10 Correct 2 ms 668 KB correct
11 Correct 2 ms 668 KB correct
12 Correct 2 ms 668 KB correct
13 Correct 2 ms 668 KB correct
14 Correct 3 ms 668 KB correct
15 Correct 2 ms 668 KB correct
16 Correct 2 ms 668 KB correct
17 Correct 4 ms 668 KB correct
18 Correct 2 ms 668 KB correct
19 Correct 4 ms 668 KB correct
20 Correct 4 ms 668 KB correct
21 Correct 4 ms 668 KB correct
22 Correct 3 ms 668 KB correct
23 Correct 3 ms 668 KB correct
24 Correct 2 ms 696 KB correct
25 Correct 3 ms 696 KB correct
26 Correct 3 ms 696 KB correct
27 Correct 3 ms 696 KB correct
28 Correct 3 ms 696 KB correct
29 Correct 2 ms 696 KB correct
30 Correct 3 ms 696 KB correct
31 Correct 4 ms 696 KB correct
32 Correct 3 ms 700 KB correct
33 Correct 3 ms 700 KB correct
34 Correct 96 ms 2044 KB correct
35 Correct 104 ms 2300 KB correct
36 Correct 63 ms 2300 KB correct
37 Correct 7 ms 2300 KB correct
38 Correct 153 ms 2644 KB correct
39 Correct 53 ms 2928 KB correct
40 Correct 67 ms 2928 KB correct
41 Correct 13 ms 3136 KB correct
42 Correct 12 ms 3368 KB correct
43 Correct 56 ms 3368 KB correct
44 Correct 56 ms 3368 KB correct
45 Correct 55 ms 3368 KB correct
46 Correct 42 ms 3368 KB correct
47 Correct 21 ms 3368 KB correct
48 Correct 4 ms 3368 KB correct
49 Correct 12 ms 3368 KB correct
50 Correct 24 ms 3368 KB correct
51 Correct 78 ms 3368 KB correct
52 Correct 53 ms 3368 KB correct
53 Correct 40 ms 3368 KB correct
54 Correct 62 ms 3800 KB correct
55 Correct 64 ms 3904 KB correct
56 Correct 51 ms 3904 KB correct
57 Correct 54 ms 3904 KB correct
58 Correct 2 ms 3904 KB correct
59 Correct 2 ms 3904 KB correct
60 Incorrect 81 ms 7288 KB WA in grader: NO
61 Halted 0 ms 0 KB -