oj.uz

Submission #779792

# Submission time Handle Problem Language Result Execution time Memory
779792 2023-07-11T20:26:31 Z I_Love_EliskaM_ Simurgh (IOI17_simurgh) C++14
51 / 100
 216 ms 3036 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;

	///////////////

	if (m!=n*(n-1)/2) exit(0);


	for (int i=1; i<n; ++i) {
		vector<int> k;
		for(int j=1; j<n; ++j) {
			if (j==i) continue;
			k.pb(adj[0][j]);
		}
		vector<pi> t;
		int mx=0;
		forn(j,n) {
			if (j==i) continue;
			k.pb(adj[i][j]);
			int x=count_common_roads(k);
			k.pop_back();
			t.pb({x,j});
			mx=max(mx,x);
		}
		for(auto&x:t) if (x.f==mx) s.insert(adj[i][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 212 KB correct
2 Correct 0 ms 340 KB correct
3 Correct 0 ms 212 KB correct
4 Correct 0 ms 340 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 1 ms 340 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 0 ms 212 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 0 ms 340 KB correct
13 Correct 0 ms 340 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Correct 0 ms 340 KB correct
3 Correct 0 ms 212 KB correct
4 Correct 0 ms 340 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 1 ms 340 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 0 ms 212 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 0 ms 340 KB correct
13 Correct 0 ms 340 KB correct
14 Correct 2 ms 468 KB correct
15 Correct 3 ms 468 KB correct
16 Correct 2 ms 468 KB correct
17 Correct 2 ms 468 KB correct
18 Correct 1 ms 340 KB correct
19 Correct 2 ms 468 KB correct
20 Correct 2 ms 452 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 340 KB correct
26 Correct 1 ms 468 KB correct
27 Correct 1 ms 468 KB correct
28 Correct 1 ms 340 KB correct
29 Correct 1 ms 340 KB correct
30 Correct 1 ms 460 KB correct
31 Correct 1 ms 468 KB correct
32 Correct 2 ms 468 KB correct
33 Correct 2 ms 460 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Correct 0 ms 340 KB correct
3 Correct 0 ms 212 KB correct
4 Correct 0 ms 340 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 1 ms 340 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 0 ms 212 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 0 ms 340 KB correct
13 Correct 0 ms 340 KB correct
14 Correct 2 ms 468 KB correct
15 Correct 3 ms 468 KB correct
16 Correct 2 ms 468 KB correct
17 Correct 2 ms 468 KB correct
18 Correct 1 ms 340 KB correct
19 Correct 2 ms 468 KB correct
20 Correct 2 ms 452 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 340 KB correct
26 Correct 1 ms 468 KB correct
27 Correct 1 ms 468 KB correct
28 Correct 1 ms 340 KB correct
29 Correct 1 ms 340 KB correct
30 Correct 1 ms 460 KB correct
31 Correct 1 ms 468 KB correct
32 Correct 2 ms 468 KB correct
33 Correct 2 ms 460 KB correct
34 Correct 207 ms 2776 KB correct
35 Correct 192 ms 2944 KB correct
36 Correct 140 ms 2436 KB correct
37 Correct 7 ms 852 KB correct
38 Correct 216 ms 3036 KB correct
39 Correct 189 ms 2872 KB correct
40 Correct 143 ms 2352 KB correct
41 Correct 207 ms 2956 KB correct
42 Correct 203 ms 3024 KB correct
43 Correct 116 ms 2040 KB correct
44 Correct 103 ms 1676 KB correct
45 Correct 107 ms 1884 KB correct
46 Correct 78 ms 1624 KB correct
47 Correct 39 ms 1168 KB correct
48 Correct 4 ms 852 KB correct
49 Correct 8 ms 932 KB correct
50 Correct 35 ms 1224 KB correct
51 Correct 99 ms 1868 KB correct
52 Correct 85 ms 1712 KB correct
53 Correct 72 ms 1580 KB correct
54 Correct 108 ms 1988 KB correct
55 Correct 106 ms 1968 KB correct
56 Correct 97 ms 1892 KB correct
57 Correct 108 ms 1916 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 12 ms 2252 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 212 KB correct
2 Correct 0 ms 340 KB correct
3 Correct 0 ms 212 KB correct
4 Correct 0 ms 340 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 1 ms 340 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 0 ms 212 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 0 ms 340 KB correct
13 Correct 0 ms 340 KB correct
14 Correct 2 ms 468 KB correct
15 Correct 3 ms 468 KB correct
16 Correct 2 ms 468 KB correct
17 Correct 2 ms 468 KB correct
18 Correct 1 ms 340 KB correct
19 Correct 2 ms 468 KB correct
20 Correct 2 ms 452 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 340 KB correct
26 Correct 1 ms 468 KB correct
27 Correct 1 ms 468 KB correct
28 Correct 1 ms 340 KB correct
29 Correct 1 ms 340 KB correct
30 Correct 1 ms 460 KB correct
31 Correct 1 ms 468 KB correct
32 Correct 2 ms 468 KB correct
33 Correct 2 ms 460 KB correct
34 Correct 207 ms 2776 KB correct
35 Correct 192 ms 2944 KB correct
36 Correct 140 ms 2436 KB correct
37 Correct 7 ms 852 KB correct
38 Correct 216 ms 3036 KB correct
39 Correct 189 ms 2872 KB correct
40 Correct 143 ms 2352 KB correct
41 Correct 207 ms 2956 KB correct
42 Correct 203 ms 3024 KB correct
43 Correct 116 ms 2040 KB correct
44 Correct 103 ms 1676 KB correct
45 Correct 107 ms 1884 KB correct
46 Correct 78 ms 1624 KB correct
47 Correct 39 ms 1168 KB correct
48 Correct 4 ms 852 KB correct
49 Correct 8 ms 932 KB correct
50 Correct 35 ms 1224 KB correct
51 Correct 99 ms 1868 KB correct
52 Correct 85 ms 1712 KB correct
53 Correct 72 ms 1580 KB correct
54 Correct 108 ms 1988 KB correct
55 Correct 106 ms 1968 KB correct
56 Correct 97 ms 1892 KB correct
57 Correct 108 ms 1916 KB correct
58 Correct 1 ms 212 KB correct
59 Correct 1 ms 340 KB correct
60 Incorrect 12 ms 2252 KB Security Violation! Don't try to hack
61 Halted 0 ms 0 KB -