oj.uz

Submission #404916

# Submission time Handle Problem Language Result Execution time Memory
404916 2021-05-15T09:56:26 Z Jasiekstrz Saveit (IOI10_saveit) C++17
50 / 100
 329 ms 14404 KB 
#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
#define fi first
#define se second
using namespace std;
static const int NN=1e3;
static const int EE=NN*NN;
static vector<pair<int,int>> e[NN+10];
static bool vis[NN+10];
static bool enc[EE+10];
void send_int(int x)
{
	for(int i=9;i>=0;i--)
		encode_bit((x&(1<<i))!=0);
	return;
}
static void bfs(int x,int n)
{
	for(int i=0;i<n;i++)
		vis[i]=false;
	queue<int> qq;
	vis[x]=true;
	qq.push(x);
	while(!qq.empty())
	{
		x=qq.front();
		qq.pop();
		for(auto v:e[x])
		{
			if(!vis[v.fi])
			{
				vis[v.fi]=true;
				enc[v.se]=true;
				qq.push(v.fi);
			}
		}
	}
	return;
}
void encode(int nv,int nh,int ne,int *v1,int *v2)
{
	for(int i=0;i<ne;i++)
	{
		e[v1[i]].emplace_back(v2[i],i);
		e[v2[i]].emplace_back(v1[i],i);
	}
	for(int i=0;i<nh;i++)
		bfs(i,nv);
	for(int i=0;i<nv;i++)
	{
		vector<int> tmp;
		for(auto v:e[i])
		{
			if(enc[v.se])
			{
				tmp.push_back(v.fi);
				enc[v.se]=false;
			}
		}
		send_int(tmp.size());
		for(auto v:tmp)
			send_int(v);
	}
	return;
}

#include<bits/stdc++.h>
#include "grader.h"
#include "decoder.h"
#define fi first
#define se second
using namespace std;
static const int NN=1e3;
static vector<int> e[NN+10];
static bool vis[NN+10];
int receive_int()
{
	int ans=0;
	for(int i=0;i<10;i++)
		ans=(2*ans+decode_bit());
	return ans;
}
static void bfs(int x,int n)
{
	for(int i=0;i<n;i++)
		vis[i]=false;
	queue<pair<int,int>> qq;
	vis[x]=true;
	qq.push({x,0});
	while(!qq.empty())
	{
		auto y=qq.front();
		qq.pop();
		hops(x,y.fi,y.se);
		for(auto v:e[y.fi])
		{
			if(!vis[v])
			{
				vis[v]=true;
				qq.push({v,y.se+1});
			}
		}
	}
	return;
}
void decode(int nv,int nh)
{
	for(int i=0;i<nv;i++)
	{
		int d=receive_int();
		for(int j=0;j<d;j++)
		{
			int b=receive_int();
			e[i].push_back(b);
			e[b].push_back(i);
		}
	}
	for(int i=0;i<nh;i++)
		bfs(i,nv);
	return;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 14404 KB Output is partially correct - 187300 call(s) of encode_bit()
2 Correct 4 ms 4580 KB Output is correct - 120 call(s) of encode_bit()
3 Correct 23 ms 5212 KB Output is correct - 43840 call(s) of encode_bit()
4 Correct 4 ms 4588 KB Output is correct - 140 call(s) of encode_bit()
5 Correct 39 ms 5992 KB Output is partially correct - 100920 call(s) of encode_bit()
6 Correct 41 ms 6128 KB Output is partially correct - 104140 call(s) of encode_bit()
7 Correct 80 ms 7428 KB Output is partially correct - 191000 call(s) of encode_bit()
8 Correct 18 ms 4944 KB Output is correct - 27870 call(s) of encode_bit()
9 Correct 27 ms 5144 KB Output is correct - 30510 call(s) of encode_bit()
10 Correct 19 ms 5188 KB Output is correct - 29470 call(s) of encode_bit()
11 Correct 33 ms 5392 KB Output is correct - 57350 call(s) of encode_bit()
12 Correct 22 ms 4968 KB Output is correct - 19990 call(s) of encode_bit()
13 Correct 80 ms 7084 KB Output is partially correct - 130780 call(s) of encode_bit()
14 Correct 20 ms 5220 KB Output is correct - 32720 call(s) of encode_bit()
15 Correct 31 ms 5224 KB Output is correct - 34270 call(s) of encode_bit()
16 Correct 76 ms 6152 KB Output is correct - 63510 call(s) of encode_bit()
17 Correct 53 ms 6144 KB Output is correct - 59610 call(s) of encode_bit()
18 Correct 69 ms 6816 KB Output is partially correct - 91160 call(s) of encode_bit()
19 Correct 49 ms 6244 KB Output is partially correct - 95490 call(s) of encode_bit()
20 Correct 80 ms 7620 KB Output is partially correct - 114910 call(s) of encode_bit()
21 Correct 119 ms 7876 KB Output is partially correct - 121410 call(s) of encode_bit()
22 Correct 91 ms 7804 KB Output is partially correct - 178600 call(s) of encode_bit()
23 Correct 110 ms 8608 KB Output is partially correct - 165990 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 14404 KB Output is partially correct - 187300 call(s) of encode_bit()
2 Correct 4 ms 4580 KB Output is correct - 120 call(s) of encode_bit()
3 Correct 23 ms 5212 KB Output is correct - 43840 call(s) of encode_bit()
4 Correct 4 ms 4588 KB Output is correct - 140 call(s) of encode_bit()
5 Correct 39 ms 5992 KB Output is partially correct - 100920 call(s) of encode_bit()
6 Correct 41 ms 6128 KB Output is partially correct - 104140 call(s) of encode_bit()
7 Correct 80 ms 7428 KB Output is partially correct - 191000 call(s) of encode_bit()
8 Correct 18 ms 4944 KB Output is correct - 27870 call(s) of encode_bit()
9 Correct 27 ms 5144 KB Output is correct - 30510 call(s) of encode_bit()
10 Correct 19 ms 5188 KB Output is correct - 29470 call(s) of encode_bit()
11 Correct 33 ms 5392 KB Output is correct - 57350 call(s) of encode_bit()
12 Correct 22 ms 4968 KB Output is correct - 19990 call(s) of encode_bit()
13 Correct 80 ms 7084 KB Output is partially correct - 130780 call(s) of encode_bit()
14 Correct 20 ms 5220 KB Output is correct - 32720 call(s) of encode_bit()
15 Correct 31 ms 5224 KB Output is correct - 34270 call(s) of encode_bit()
16 Correct 76 ms 6152 KB Output is correct - 63510 call(s) of encode_bit()
17 Correct 53 ms 6144 KB Output is correct - 59610 call(s) of encode_bit()
18 Correct 69 ms 6816 KB Output is partially correct - 91160 call(s) of encode_bit()
19 Correct 49 ms 6244 KB Output is partially correct - 95490 call(s) of encode_bit()
20 Correct 80 ms 7620 KB Output is partially correct - 114910 call(s) of encode_bit()
21 Correct 119 ms 7876 KB Output is partially correct - 121410 call(s) of encode_bit()
22 Correct 91 ms 7804 KB Output is partially correct - 178600 call(s) of encode_bit()
23 Correct 110 ms 8608 KB Output is partially correct - 165990 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 14404 KB Output is partially correct - 187300 call(s) of encode_bit()
2 Correct 4 ms 4580 KB Output is correct - 120 call(s) of encode_bit()
3 Correct 23 ms 5212 KB Output is correct - 43840 call(s) of encode_bit()
4 Correct 4 ms 4588 KB Output is correct - 140 call(s) of encode_bit()
5 Correct 39 ms 5992 KB Output is partially correct - 100920 call(s) of encode_bit()
6 Correct 41 ms 6128 KB Output is partially correct - 104140 call(s) of encode_bit()
7 Correct 80 ms 7428 KB Output is partially correct - 191000 call(s) of encode_bit()
8 Correct 18 ms 4944 KB Output is correct - 27870 call(s) of encode_bit()
9 Correct 27 ms 5144 KB Output is correct - 30510 call(s) of encode_bit()
10 Correct 19 ms 5188 KB Output is correct - 29470 call(s) of encode_bit()
11 Correct 33 ms 5392 KB Output is correct - 57350 call(s) of encode_bit()
12 Correct 22 ms 4968 KB Output is correct - 19990 call(s) of encode_bit()
13 Correct 80 ms 7084 KB Output is partially correct - 130780 call(s) of encode_bit()
14 Correct 20 ms 5220 KB Output is correct - 32720 call(s) of encode_bit()
15 Correct 31 ms 5224 KB Output is correct - 34270 call(s) of encode_bit()
16 Correct 76 ms 6152 KB Output is correct - 63510 call(s) of encode_bit()
17 Correct 53 ms 6144 KB Output is correct - 59610 call(s) of encode_bit()
18 Correct 69 ms 6816 KB Output is partially correct - 91160 call(s) of encode_bit()
19 Correct 49 ms 6244 KB Output is partially correct - 95490 call(s) of encode_bit()
20 Correct 80 ms 7620 KB Output is partially correct - 114910 call(s) of encode_bit()
21 Correct 119 ms 7876 KB Output is partially correct - 121410 call(s) of encode_bit()
22 Correct 91 ms 7804 KB Output is partially correct - 178600 call(s) of encode_bit()
23 Correct 110 ms 8608 KB Output is partially correct - 165990 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 14404 KB Output is partially correct - 187300 call(s) of encode_bit()
2 Correct 4 ms 4580 KB Output is correct - 120 call(s) of encode_bit()
3 Correct 23 ms 5212 KB Output is correct - 43840 call(s) of encode_bit()
4 Correct 4 ms 4588 KB Output is correct - 140 call(s) of encode_bit()
5 Correct 39 ms 5992 KB Output is partially correct - 100920 call(s) of encode_bit()
6 Correct 41 ms 6128 KB Output is partially correct - 104140 call(s) of encode_bit()
7 Correct 80 ms 7428 KB Output is partially correct - 191000 call(s) of encode_bit()
8 Correct 18 ms 4944 KB Output is correct - 27870 call(s) of encode_bit()
9 Correct 27 ms 5144 KB Output is correct - 30510 call(s) of encode_bit()
10 Correct 19 ms 5188 KB Output is correct - 29470 call(s) of encode_bit()
11 Correct 33 ms 5392 KB Output is correct - 57350 call(s) of encode_bit()
12 Correct 22 ms 4968 KB Output is correct - 19990 call(s) of encode_bit()
13 Correct 80 ms 7084 KB Output is partially correct - 130780 call(s) of encode_bit()
14 Correct 20 ms 5220 KB Output is correct - 32720 call(s) of encode_bit()
15 Correct 31 ms 5224 KB Output is correct - 34270 call(s) of encode_bit()
16 Correct 76 ms 6152 KB Output is correct - 63510 call(s) of encode_bit()
17 Correct 53 ms 6144 KB Output is correct - 59610 call(s) of encode_bit()
18 Correct 69 ms 6816 KB Output is partially correct - 91160 call(s) of encode_bit()
19 Correct 49 ms 6244 KB Output is partially correct - 95490 call(s) of encode_bit()
20 Correct 80 ms 7620 KB Output is partially correct - 114910 call(s) of encode_bit()
21 Correct 119 ms 7876 KB Output is partially correct - 121410 call(s) of encode_bit()
22 Correct 91 ms 7804 KB Output is partially correct - 178600 call(s) of encode_bit()
23 Correct 110 ms 8608 KB Output is partially correct - 165990 call(s) of encode_bit()