oj.uz

Submission #779780

# Submission time Handle Problem Language Result Execution time Memory
779780 2023-07-11T19:50:26 Z I_Love_EliskaM_ Simurgh (IOI17_simurgh) C++14
13 / 100
 176 ms 3156 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];
	}
};

vector<int> f(vector<int>&z) {
	vector<int> v;
	forn(i,z.size()) if (z[i]) v.pb(i);
	return v;
}
int _q=0;
int ask(vector<int>&z) {
	++_q; assert(_q<=30000);
	auto v=f(z);
	return count_common_roads(v);
}

const int N=500;
int adj[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;
	}
	if (n<=7) {
		forn(mask,1<<m) {
			vector<int> z(m,0);
			forn(i,m) if ((mask>>i)&1) z[i]=1;
			int cnt=0;
			forn(i,m) cnt+=z[i];
			if (cnt!=n-1) continue;
			DSU dsu(n);
			forn(i,m) if (z[i]) dsu.uni(u[i],v[i]);
			if (dsu.sz[dsu.get(0)]!=n) continue;
			int x=ask(z);
			if (x==n-1) return f(z);
		}
	}
	if (m!=n*(n-1)/2) exit(0);
	forn(i,m) adj[u[i]][v[i]]=adj[v[i]][u[i]]=i;
	
	vector<int> ok(m,0);
	vector<int> z;
	set<int> s;
	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;

}

Compilation message

simurgh.cpp: In function 'std::vector<int> first(std::vector<int>&)':
simurgh.cpp:4:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for(int i=0;i<n;++i)
......
   33 |  forn(i,z.size()) if (z[i]) v.pb(i);
      |       ~~~~~~~~~~                
simurgh.cpp:33:2: note: in expansion of macro 'forn'
   33 |  forn(i,z.size()) if (z[i]) v.pb(i);
      |  ^~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 212 KB correct
2 Correct 140 ms 296 KB correct
3 Correct 176 ms 296 KB correct
4 Correct 1 ms 340 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 5 ms 212 KB correct
7 Correct 1 ms 316 KB correct
8 Correct 1 ms 316 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 2 ms 212 KB correct
11 Correct 1 ms 320 KB correct
12 Correct 2 ms 212 KB correct
13 Correct 50 ms 212 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 212 KB correct
2 Correct 140 ms 296 KB correct
3 Correct 176 ms 296 KB correct
4 Correct 1 ms 340 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 5 ms 212 KB correct
7 Correct 1 ms 316 KB correct
8 Correct 1 ms 316 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 2 ms 212 KB correct
11 Correct 1 ms 320 KB correct
12 Correct 2 ms 212 KB correct
13 Correct 50 ms 212 KB correct
14 Correct 2 ms 340 KB correct
15 Correct 2 ms 340 KB correct
16 Correct 2 ms 320 KB correct
17 Incorrect 1 ms 212 KB Security Violation! Don't try to hack
18 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 212 KB correct
2 Correct 140 ms 296 KB correct
3 Correct 176 ms 296 KB correct
4 Correct 1 ms 340 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 5 ms 212 KB correct
7 Correct 1 ms 316 KB correct
8 Correct 1 ms 316 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 2 ms 212 KB correct
11 Correct 1 ms 320 KB correct
12 Correct 2 ms 212 KB correct
13 Correct 50 ms 212 KB correct
14 Correct 2 ms 340 KB correct
15 Correct 2 ms 340 KB correct
16 Correct 2 ms 320 KB correct
17 Incorrect 1 ms 212 KB Security Violation! Don't try to hack
18 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 316 KB correct
3 Incorrect 57 ms 3156 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 212 KB correct
2 Correct 140 ms 296 KB correct
3 Correct 176 ms 296 KB correct
4 Correct 1 ms 340 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 5 ms 212 KB correct
7 Correct 1 ms 316 KB correct
8 Correct 1 ms 316 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 2 ms 212 KB correct
11 Correct 1 ms 320 KB correct
12 Correct 2 ms 212 KB correct
13 Correct 50 ms 212 KB correct
14 Correct 2 ms 340 KB correct
15 Correct 2 ms 340 KB correct
16 Correct 2 ms 320 KB correct
17 Incorrect 1 ms 212 KB Security Violation! Don't try to hack
18 Halted 0 ms 0 KB -