oj.uz

Submission #780498

# Submission time Handle Problem Language Result Execution time Memory
780498 2023-07-12T09:34:30 Z I_Love_EliskaM_ Simurgh (IOI17_simurgh) C++14
51 / 100
 224 ms 3096 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int a, int b) {return a+rng()%(b-a+1);}
#define all(x) x.begin(),x.end()


struct DSU {
	vector<int> p,sz;
	DSU(int n) {
		forn(i,n) p.pb(i), sz.pb(1);
	}
	int get(int u) {
		return p[u]==u?u:get(p[u]);
	}
	void uni(int u, int v) {
		u=get(u), v=get(v);
		if (u==v) return;
		if (sz[u]<sz[v]) swap(u,v);
		p[v]=u;
		sz[u]+=sz[v];
	}
};

const int N=500;
int adj[N][N];
int b[N][N];
int br[N*N];

vector<int> find_roads(int n, vector<int>u, vector<int>v) {
	int m=u.size();
	if (m==n-1) {
		vector<int> v; forn(i,m) v.pb(i);
		return v;
	}
	
	vector<int> z;
	set<int> s;
	forn(i,m) adj[u[i]][v[i]]=adj[v[i]][u[i]]=i;
	
	if (n>240) exit(0);

	vector<vector<int>> g(n);
	forn(i,m) {
		g[u[i]].pb(v[i]);
		g[v[i]].pb(u[i]);
	}

	map<int,int> was;
	forn(i,n) {
		
		DSU dsu(n);		
		vector<int> t;
		forn(j,m) {
			int x=u[j], y=v[j];
			if (x==i || y==i) continue;
			if (dsu.get(x)==dsu.get(y)) continue;
			dsu.uni(x,y);
			t.pb(j);
		}
		map<int,vector<int>> mp;
		for(auto&v:g[i]) {
			mp[dsu.get(v)].pb(adj[i][v]);
		}

		for(auto&it1:mp) {

			int c=it1.f;
			auto z=it1.s;
			auto q=t;
			for(auto&it2:mp) {
				if (it2.f==c) continue;
				q.pb(it2.s[0]);
			}
			vector<pi> v;
			int mx=0;
			int kurwa=1;
			for(auto&x:z) {
				if (was[x]) {
					if (kurwa && s.count(x)) {
						q.pb(x);
						int y=count_common_roads(q);
						q.pop_back();
						mx=max(mx,y);
						kurwa=0;
					}
					continue;
				}
				was[x]=1;
				q.pb(x);
				int y=count_common_roads(q);
				q.pop_back();
				v.pb({y,x});
				mx=max(mx,y);
			}
			for(auto&x:v) if (x.f==mx) s.insert(x.s);

		}

	}
	for(auto&x:s) z.pb(x);
	return z;

}

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB correct
2 Correct 1 ms 312 KB correct
3 Correct 1 ms 340 KB correct
4 Correct 1 ms 340 KB correct
5 Correct 1 ms 340 KB correct
6 Correct 1 ms 340 KB correct
7 Correct 1 ms 312 KB correct
8 Correct 1 ms 308 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 3 ms 488 KB correct
15 Correct 3 ms 448 KB correct
16 Correct 3 ms 444 KB correct
17 Correct 2 ms 468 KB correct
18 Correct 1 ms 340 KB correct
19 Correct 3 ms 468 KB correct
20 Correct 2 ms 448 KB correct
21 Correct 2 ms 468 KB correct
22 Correct 2 ms 468 KB correct
23 Correct 2 ms 468 KB correct
24 Correct 2 ms 468 KB correct
25 Correct 1 ms 320 KB correct
26 Correct 2 ms 468 KB correct
27 Correct 2 ms 468 KB correct
28 Correct 1 ms 340 KB correct
29 Correct 1 ms 340 KB correct
30 Correct 2 ms 468 KB correct
31 Correct 2 ms 468 KB correct
32 Correct 2 ms 448 KB correct
33 Correct 2 ms 468 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB correct
2 Correct 1 ms 312 KB correct
3 Correct 1 ms 340 KB correct
4 Correct 1 ms 340 KB correct
5 Correct 1 ms 340 KB correct
6 Correct 1 ms 340 KB correct
7 Correct 1 ms 312 KB correct
8 Correct 1 ms 308 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 3 ms 488 KB correct
15 Correct 3 ms 448 KB correct
16 Correct 3 ms 444 KB correct
17 Correct 2 ms 468 KB correct
18 Correct 1 ms 340 KB correct
19 Correct 3 ms 468 KB correct
20 Correct 2 ms 448 KB correct
21 Correct 2 ms 468 KB correct
22 Correct 2 ms 468 KB correct
23 Correct 2 ms 468 KB correct
24 Correct 2 ms 468 KB correct
25 Correct 1 ms 320 KB correct
26 Correct 2 ms 468 KB correct
27 Correct 2 ms 468 KB correct
28 Correct 1 ms 340 KB correct
29 Correct 1 ms 340 KB correct
30 Correct 2 ms 468 KB correct
31 Correct 2 ms 468 KB correct
32 Correct 2 ms 448 KB correct
33 Correct 2 ms 468 KB correct
34 Correct 205 ms 2996 KB correct
35 Correct 199 ms 3096 KB correct
36 Correct 138 ms 2376 KB correct
37 Correct 11 ms 852 KB correct
38 Correct 221 ms 3028 KB correct
39 Correct 180 ms 2752 KB correct
40 Correct 148 ms 2324 KB correct
41 Correct 219 ms 2980 KB correct
42 Correct 224 ms 3000 KB correct
43 Correct 114 ms 2112 KB correct
44 Correct 98 ms 1752 KB correct
45 Correct 108 ms 1924 KB correct
46 Correct 78 ms 1664 KB correct
47 Correct 37 ms 1168 KB correct
48 Correct 5 ms 852 KB correct
49 Correct 8 ms 904 KB correct
50 Correct 39 ms 1188 KB correct
51 Correct 114 ms 1912 KB correct
52 Correct 86 ms 1680 KB correct
53 Correct 72 ms 1648 KB correct
54 Correct 105 ms 1980 KB correct
55 Correct 103 ms 1932 KB correct
56 Correct 105 ms 1836 KB correct
57 Correct 129 ms 1928 KB correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 340 KB correct
3 Incorrect 14 ms 2856 KB Security Violation! Don't try to hack
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB correct
2 Correct 1 ms 312 KB correct
3 Correct 1 ms 340 KB correct
4 Correct 1 ms 340 KB correct
5 Correct 1 ms 340 KB correct
6 Correct 1 ms 340 KB correct
7 Correct 1 ms 312 KB correct
8 Correct 1 ms 308 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 3 ms 488 KB correct
15 Correct 3 ms 448 KB correct
16 Correct 3 ms 444 KB correct
17 Correct 2 ms 468 KB correct
18 Correct 1 ms 340 KB correct
19 Correct 3 ms 468 KB correct
20 Correct 2 ms 448 KB correct
21 Correct 2 ms 468 KB correct
22 Correct 2 ms 468 KB correct
23 Correct 2 ms 468 KB correct
24 Correct 2 ms 468 KB correct
25 Correct 1 ms 320 KB correct
26 Correct 2 ms 468 KB correct
27 Correct 2 ms 468 KB correct
28 Correct 1 ms 340 KB correct
29 Correct 1 ms 340 KB correct
30 Correct 2 ms 468 KB correct
31 Correct 2 ms 468 KB correct
32 Correct 2 ms 448 KB correct
33 Correct 2 ms 468 KB correct
34 Correct 205 ms 2996 KB correct
35 Correct 199 ms 3096 KB correct
36 Correct 138 ms 2376 KB correct
37 Correct 11 ms 852 KB correct
38 Correct 221 ms 3028 KB correct
39 Correct 180 ms 2752 KB correct
40 Correct 148 ms 2324 KB correct
41 Correct 219 ms 2980 KB correct
42 Correct 224 ms 3000 KB correct
43 Correct 114 ms 2112 KB correct
44 Correct 98 ms 1752 KB correct
45 Correct 108 ms 1924 KB correct
46 Correct 78 ms 1664 KB correct
47 Correct 37 ms 1168 KB correct
48 Correct 5 ms 852 KB correct
49 Correct 8 ms 904 KB correct
50 Correct 39 ms 1188 KB correct
51 Correct 114 ms 1912 KB correct
52 Correct 86 ms 1680 KB correct
53 Correct 72 ms 1648 KB correct
54 Correct 105 ms 1980 KB correct
55 Correct 103 ms 1932 KB correct
56 Correct 105 ms 1836 KB correct
57 Correct 129 ms 1928 KB correct
58 Correct 1 ms 212 KB correct
59 Correct 1 ms 340 KB correct
60 Incorrect 14 ms 2856 KB Security Violation! Don't try to hack
61 Halted 0 ms 0 KB -