oj.uz

Submission #803076

# Submission time Handle Problem Language Result Execution time Memory
803076 2023-08-02T21:19:52 Z Antekb Saveit (IOI10_saveit) C++17
0 / 100
 2699 ms 12556 KB 
#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define pp pop_back;
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
void nadaj(int x, int b){
	for(int i=0; i<b; i++){
		encode_bit(!!(x&(1<<i)));
	}
}
void encode(int n, int h, int m, int *v1, int *v2){
	vi E[n];
	int czy[n][h], dist[n][h];
	for(int i=0; i<n; i++){
		for(int j=0; j<h; j++){
			czy[i][j]=(i==j);
			dist[i][j]=1e9*(i!=j);
		}
	}
	vi edg;
	for(int i=0; i<m; i++){
		E[v1[i]].pb(edg.size());
		edg.pb(v2[i]);
		E[v2[i]].pb(edg.size());
		edg.pb(v1[i]);
	}
	for(int s=0; s<h; s++){
		vi V;
		V.pb(s);
		for(int i=0; i<V.size(); i++){
			int v=V[i];
			for(int e:E[v]){
				if(dist[edg[e]][s]==1e9){
					dist[edg[e]][s]=dist[v][s]+1;
					V.pb(edg[e]);
				}
			}
		}
	}
	vi E2[n];
	for(int v=0; v<n; v++){
		int ile=0;
		for(int e:E[v]){
			int u=edg[e];
			bool b=0;
			for(int i=0; i<h; i++){
				if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
					b=1;
				}
				if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
					b=1;
				}
			}
			if(b)ile++;
		}
		if(ile>=100){
			for(int e:E[v]){
				int u=edg[e];
				for(int i=0; i<h; i++){
					if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
						czy[u][i]=1;
						E2[v].pb(u);
					}
					if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
						czy[v][i]=1;
						E2[v].pb(u);
					}
				}
			}
		}
	}
	int sum=0;
	for(int t=h; t>0; t--){
		for(int u=0; u<n; u++){
			for(int v=0; v<u; v++){
			int ile=0;
			for(int i=0; i<h; i++){
				if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
					ile++;
				}
				if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
					ile++;
				}
			}
			if(ile==t){
				//cerr<<t<<"\n";
				sum+=t;
				E2[v].pb(u);
				for(int i=0; i<h; i++){
					if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
						czy[u][i]=1;
					}
					if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
						czy[v][i]=1;
					}
				}
			}
			}
		}
	}
	cerr<<sum<<"\n";
	for(int i=0; i<n; i++){
		sort(E2[i].begin(), E2[i].end());
		nadaj(min((int)E2[i].size(), 100), 7);
		if(E2[i].size()>=100){
			vi V(n);
			for(int u:E2[i]){
				V[u]=1;
			}
			for(int j:V){
				nadaj(j, 1);
			}
		}
		else{
			for(int u:E2[i]){
				nadaj(u, 10);
			}
		}
	}
	return;
}
#include "grader.h"
#include "decoder.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define pp pop_back;
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
int czytaj(int b){
	int x=0;
	for(int i=0; i<b; i++){
		x+=(int(decode_bit())<<i);
	}
	return x;
}
void decode(int n, int h) {
	vi E[n];
	for(int i=0;i<n; i++){
		int k=czytaj(7);
		//cerr<<k<<"\n";
		if(k==100){
			for(int j=0; j<n; j++){
				if(czytaj(1)){
					E[i].pb(j);
					E[j].pb(i);
				}
			}
		}
		else{
			while(k--){
				int j=czytaj(10);
				E[i].pb(j);
				E[j].pb(i);
			}
		}
	}
	for(int s=0; s<h; s++){
		vi V;
		V.pb(s);
		vi dist(n, 1e9);
		dist[s]=0;
		for(int i=0; i<V.size(); i++){
			int v=V[i];
			for(int u:E[v]){
				if(dist[u]==1e9){
					dist[u]=dist[v]+1;
					V.pb(u);
				}
			}
		}
		for(int i=0; i<n; i++){
			hops(s, i, dist[i]);
		}
	}
}

Compilation message

encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:35:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int i=0; i<V.size(); i++){
      |                ~^~~~~~~~~

decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:44:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(int i=0; i<V.size(); i++){
      |                ~^~~~~~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 967 ms 12556 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 105 call(s) of encode_bit()
3 Incorrect 2215 ms 5444 KB Output isn't correct
4 Correct 2 ms 4580 KB Output is correct - 125 call(s) of encode_bit()
5 Incorrect 2401 ms 5944 KB Output isn't correct
6 Incorrect 2699 ms 6112 KB Output isn't correct
7 Incorrect 1432 ms 6616 KB Output isn't correct
8 Incorrect 1175 ms 5232 KB Output isn't correct
9 Incorrect 958 ms 5224 KB Output isn't correct
10 Incorrect 952 ms 5220 KB Output isn't correct
11 Correct 1139 ms 5736 KB Output is correct - 41450 call(s) of encode_bit()
12 Correct 825 ms 5148 KB Output is correct - 16990 call(s) of encode_bit()
13 Incorrect 2485 ms 6928 KB Output isn't correct
14 Incorrect 971 ms 5240 KB Output isn't correct
15 Incorrect 873 ms 5288 KB Output isn't correct
16 Incorrect 916 ms 6372 KB Output isn't correct
17 Incorrect 858 ms 6220 KB Output isn't correct
18 Incorrect 896 ms 6728 KB Output isn't correct
19 Incorrect 1422 ms 5932 KB Output isn't correct
20 Incorrect 974 ms 7324 KB Output isn't correct
21 Incorrect 948 ms 7488 KB Output isn't correct
22 Incorrect 1467 ms 6640 KB Output isn't correct
23 Incorrect 1091 ms 8316 KB Output isn't correct

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 967 ms 12556 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 105 call(s) of encode_bit()
3 Incorrect 2215 ms 5444 KB Output isn't correct
4 Correct 2 ms 4580 KB Output is correct - 125 call(s) of encode_bit()
5 Incorrect 2401 ms 5944 KB Output isn't correct
6 Incorrect 2699 ms 6112 KB Output isn't correct
7 Incorrect 1432 ms 6616 KB Output isn't correct
8 Incorrect 1175 ms 5232 KB Output isn't correct
9 Incorrect 958 ms 5224 KB Output isn't correct
10 Incorrect 952 ms 5220 KB Output isn't correct
11 Correct 1139 ms 5736 KB Output is correct - 41450 call(s) of encode_bit()
12 Correct 825 ms 5148 KB Output is correct - 16990 call(s) of encode_bit()
13 Incorrect 2485 ms 6928 KB Output isn't correct
14 Incorrect 971 ms 5240 KB Output isn't correct
15 Incorrect 873 ms 5288 KB Output isn't correct
16 Incorrect 916 ms 6372 KB Output isn't correct
17 Incorrect 858 ms 6220 KB Output isn't correct
18 Incorrect 896 ms 6728 KB Output isn't correct
19 Incorrect 1422 ms 5932 KB Output isn't correct
20 Incorrect 974 ms 7324 KB Output isn't correct
21 Incorrect 948 ms 7488 KB Output isn't correct
22 Incorrect 1467 ms 6640 KB Output isn't correct
23 Incorrect 1091 ms 8316 KB Output isn't correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 967 ms 12556 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 105 call(s) of encode_bit()
3 Incorrect 2215 ms 5444 KB Output isn't correct
4 Correct 2 ms 4580 KB Output is correct - 125 call(s) of encode_bit()
5 Incorrect 2401 ms 5944 KB Output isn't correct
6 Incorrect 2699 ms 6112 KB Output isn't correct
7 Incorrect 1432 ms 6616 KB Output isn't correct
8 Incorrect 1175 ms 5232 KB Output isn't correct
9 Incorrect 958 ms 5224 KB Output isn't correct
10 Incorrect 952 ms 5220 KB Output isn't correct
11 Correct 1139 ms 5736 KB Output is correct - 41450 call(s) of encode_bit()
12 Correct 825 ms 5148 KB Output is correct - 16990 call(s) of encode_bit()
13 Incorrect 2485 ms 6928 KB Output isn't correct
14 Incorrect 971 ms 5240 KB Output isn't correct
15 Incorrect 873 ms 5288 KB Output isn't correct
16 Incorrect 916 ms 6372 KB Output isn't correct
17 Incorrect 858 ms 6220 KB Output isn't correct
18 Incorrect 896 ms 6728 KB Output isn't correct
19 Incorrect 1422 ms 5932 KB Output isn't correct
20 Incorrect 974 ms 7324 KB Output isn't correct
21 Incorrect 948 ms 7488 KB Output isn't correct
22 Incorrect 1467 ms 6640 KB Output isn't correct
23 Incorrect 1091 ms 8316 KB Output isn't correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 967 ms 12556 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 105 call(s) of encode_bit()
3 Incorrect 2215 ms 5444 KB Output isn't correct
4 Correct 2 ms 4580 KB Output is correct - 125 call(s) of encode_bit()
5 Incorrect 2401 ms 5944 KB Output isn't correct
6 Incorrect 2699 ms 6112 KB Output isn't correct
7 Incorrect 1432 ms 6616 KB Output isn't correct
8 Incorrect 1175 ms 5232 KB Output isn't correct
9 Incorrect 958 ms 5224 KB Output isn't correct
10 Incorrect 952 ms 5220 KB Output isn't correct
11 Correct 1139 ms 5736 KB Output is correct - 41450 call(s) of encode_bit()
12 Correct 825 ms 5148 KB Output is correct - 16990 call(s) of encode_bit()
13 Incorrect 2485 ms 6928 KB Output isn't correct
14 Incorrect 971 ms 5240 KB Output isn't correct
15 Incorrect 873 ms 5288 KB Output isn't correct
16 Incorrect 916 ms 6372 KB Output isn't correct
17 Incorrect 858 ms 6220 KB Output isn't correct
18 Incorrect 896 ms 6728 KB Output isn't correct
19 Incorrect 1422 ms 5932 KB Output isn't correct
20 Incorrect 974 ms 7324 KB Output isn't correct
21 Incorrect 948 ms 7488 KB Output isn't correct
22 Incorrect 1467 ms 6640 KB Output isn't correct
23 Incorrect 1091 ms 8316 KB Output isn't correct