oj.uz

Submission #949726

# Submission time Handle Problem Language Result Execution time Memory
949726 2024-03-19T15:28:02 Z qin Simurgh (IOI17_simurgh) C++17
30 / 100
 88 ms 24212 KB 
    #include <bits/stdc++.h>
    #include "simurgh.h"
    #define fi first
    #define se second
    #define ssize(x) int(x.size())
    #define pn printf("\n")
    #define all(x) x.begin(),x.end()
    #define rall(x) x.rbegin(), x.rend()
    #define vv vector
    using namespace std;
    typedef long long ll;
    typedef pair<int, int> pii;
    int inf = 2e09; ll infll = 2e18; int mod = 119<<23|1;
    struct graph{
    		vv<vv<pii>> g;
    		vv<int> vis;
    		vv<vv<int>> queries;
    		vv<int> res, taken;
    		vv<int> av;
    		void init(int n, int m){
    				g.resize(n), vis.resize(n); // trzeba pamietać, że są indeksowane od 0 do n-1 !!!
    				queries.resize(m), res.resize(m, -1), taken.resize(m, 0), av.resize(m);
    		}
    		void add_edge(int a, int b, int i){ g[a].emplace_back(b, i), g[b].emplace_back(a, i); }
    		void dfs(int x, int c, vv<int> &edges){
    				vis[x] = c;
    				for(pii &u : g[x]) if(!vis[u.fi]) edges.emplace_back(u.se), dfs(u.fi, c, edges);
    		}
    		vv<int> prep_colour(int x, int &c){
    				int l = 0; fill(all(vis), 0);
    				vis[x] = inf;
    				vv<int> edges;
    				for(pii &u : g[x]) if(!vis[u.fi]) dfs(u.fi, ++l, edges);
    				c = l;
    				return edges;
    		}
    		void dfs_check(int x){
    				vis[x] = 1;
    				for(pii &u : g[x]) if(!vis[u.fi] && av[u.se]) dfs_check(u.fi);
    		}
    		bool check_tree(vv<int> tmp){
    				fill(all(av), 0), fill(all(vis), 0);
    				bool ret = 1;
    				if(ssize(tmp) != ssize(g)-1) ret = 0;
    				for(int u : tmp) av[u] = 1;
    				dfs_check(0);
    				for(int u : vis) if(!u) ret = 0;
    				return ret;
    		}
    		vv<int> get_roads(){
    				int n = ssize(g);
    				for(int i = 0; i < n; ++i){
    						int k = 0;
    						vv<int> edges = prep_colour(i, k);
    						vv<vv<int>> t(k+1);
    						for(pii &u : g[i]) t[vis[u.fi]].emplace_back(u.se);
    						for(int j = 1; j <= k; ++j){
    								int mx = -1;
    								vv<int> equal_to_max;
    								for(int u : t[j]){
    												vv<int> tmp = edges;
    												for(int l = 1; l <= k; ++l) if(l != j) tmp.emplace_back(t[l].back());
    												tmp.emplace_back(u);
    												//~ assert(ssize(tmp) == ssize(g)-1);
    												//~ printf("a %d %d %d\n", i, j, u);
    												//~ for(int u : tmp) printf("%d ", u);
    												//~ pn;
    												//~ assert(check_tree(tmp));
    												int ask = count_common_roads(tmp);
    												if(ask > mx) equal_to_max.clear();
    												if(ask >= mx) mx = ask, equal_to_max.emplace_back(u);
    												tmp.pop_back(), queries[u] = tmp, res[u] = ask;
    										
    								}
    								for(int u : equal_to_max) taken[u] = 1;
    						}
    				}
    				vv<int> result;
    				for(int i = 0; i < ssize(taken); ++i) if(taken[i]) result.emplace_back(i);//, printf("%d\n", i);
    				assert(ssize(result) == ssize(g)-1);
    				return result;
    		}
    };
    vv<int> find_roads(int n, vv<int> u, vv<int> v){
    		graph g; g.init(n, ssize(u));
    		for(int i = 0; i < ssize(u); ++i) g.add_edge(u[i], v[i], i);
    		return g.get_roads();
    }
    #ifdef LOCAL
    int main(){
    		int T = 1;
    		for(++T; --T; ) answer();
    		return 0;
    }
    #endif

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 0 ms 348 KB correct
4 Correct 1 ms 348 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 0 ms 348 KB correct
7 Correct 0 ms 604 KB correct
8 Correct 0 ms 348 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 0 ms 348 KB correct
11 Correct 0 ms 348 KB correct
12 Correct 0 ms 344 KB correct
13 Correct 0 ms 348 KB correct
14 Correct 2 ms 604 KB correct
15 Correct 2 ms 604 KB correct
16 Correct 2 ms 604 KB correct
17 Correct 2 ms 604 KB correct
18 Correct 1 ms 344 KB correct
19 Correct 2 ms 604 KB correct
20 Correct 2 ms 604 KB correct
21 Correct 2 ms 604 KB correct
22 Correct 1 ms 604 KB correct
23 Correct 1 ms 604 KB correct
24 Correct 2 ms 600 KB correct
25 Correct 1 ms 348 KB correct
26 Correct 1 ms 604 KB correct
27 Correct 1 ms 600 KB correct
28 Correct 1 ms 348 KB correct
29 Correct 1 ms 440 KB correct
30 Correct 1 ms 576 KB correct
31 Correct 1 ms 604 KB correct
32 Correct 1 ms 604 KB correct
33 Correct 1 ms 604 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 0 ms 348 KB correct
4 Correct 1 ms 348 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 0 ms 348 KB correct
7 Correct 0 ms 604 KB correct
8 Correct 0 ms 348 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 0 ms 348 KB correct
11 Correct 0 ms 348 KB correct
12 Correct 0 ms 344 KB correct
13 Correct 0 ms 348 KB correct
14 Correct 2 ms 604 KB correct
15 Correct 2 ms 604 KB correct
16 Correct 2 ms 604 KB correct
17 Correct 2 ms 604 KB correct
18 Correct 1 ms 344 KB correct
19 Correct 2 ms 604 KB correct
20 Correct 2 ms 604 KB correct
21 Correct 2 ms 604 KB correct
22 Correct 1 ms 604 KB correct
23 Correct 1 ms 604 KB correct
24 Correct 2 ms 600 KB correct
25 Correct 1 ms 348 KB correct
26 Correct 1 ms 604 KB correct
27 Correct 1 ms 600 KB correct
28 Correct 1 ms 348 KB correct
29 Correct 1 ms 440 KB correct
30 Correct 1 ms 576 KB correct
31 Correct 1 ms 604 KB correct
32 Correct 1 ms 604 KB correct
33 Correct 1 ms 604 KB correct
34 Incorrect 88 ms 23312 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 0 ms 348 KB correct
4 Correct 1 ms 348 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 0 ms 348 KB correct
7 Correct 0 ms 604 KB correct
8 Correct 0 ms 348 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 0 ms 348 KB correct
11 Correct 0 ms 348 KB correct
12 Correct 0 ms 344 KB correct
13 Correct 0 ms 348 KB correct
14 Correct 2 ms 604 KB correct
15 Correct 2 ms 604 KB correct
16 Correct 2 ms 604 KB correct
17 Correct 2 ms 604 KB correct
18 Correct 1 ms 344 KB correct
19 Correct 2 ms 604 KB correct
20 Correct 2 ms 604 KB correct
21 Correct 2 ms 604 KB correct
22 Correct 1 ms 604 KB correct
23 Correct 1 ms 604 KB correct
24 Correct 2 ms 600 KB correct
25 Correct 1 ms 348 KB correct
26 Correct 1 ms 604 KB correct
27 Correct 1 ms 600 KB correct
28 Correct 1 ms 348 KB correct
29 Correct 1 ms 440 KB correct
30 Correct 1 ms 576 KB correct
31 Correct 1 ms 604 KB correct
32 Correct 1 ms 604 KB correct
33 Correct 1 ms 604 KB correct
34 Incorrect 88 ms 23312 KB WA in grader: NO
35 Halted 0 ms 0 KB -