oj.uz

Submission #732109

# Submission time Handle Problem Language Result Execution time Memory
732109 2023-04-28T12:25:58 Z sentheta Airline Route Map (JOI18_airline) C++17
37 / 100
 641 ms 56948 KB 
#include "Alicelib.h"
#include <cstdio>
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

static const int k = 6;

set<pii> AliceAns;
void AliceMake(int u,int v){
	if(u>v) swap(u,v);
	AliceAns.insert({u,v});
}
void AliceFinish(int n){
	// dbg("ALICE DONE");
	InitG(1+n+k+1, (int)AliceAns.size());
	int i = 0;
	for(auto[u,v] : AliceAns){
		// cout << u _ v << endl;
		MakeG(i++, u,v);
	}
	// cout << endl << endl;
}

void Alice(int n,int m,int u[],int v[]){
	rep(i,0,m){
		u[i]++; v[i]++;
		AliceMake(u[i],v[i]);
	}

	int a = 0;
	// connect 2^i to a and nodes with ith-bit ON
	AliceMake(n+1, n+3);
	AliceMake(n+1, n+4);
	rep(i,0,k){
		int vtx = n+1+i;
		AliceMake(a,vtx);
		if(i>=2) AliceMake(vtx-1, vtx);

		for(int j=1; j<=n; j++) if(j&1<<i){
			AliceMake(vtx, j);
		}
	}

	// connect b to all except a
	int b = n+k+1;
	for(int i=0; i<=n+k; i++) if(i!=a){
		AliceMake(b, i);
	}

	AliceFinish(n);
	rep(i,0,m){
		u[i]--; v[i]--;
	}
	return; InitG(3,2); MakeG(0,1,2); MakeG(1,1,3);
}


#include "Boblib.h"
#include <cstdio>
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

static const int k = 6;

set<pii> BobAns;
void BobMake(int u,int v){
	if(u>v) swap(u,v);
	BobAns.insert({u,v});
}
void BobFinish(int n){
	// dbg(BobAns.size());
	InitMap(n, (int)BobAns.size());
	for(auto[u,v] : BobAns){
		MakeMap(u-1, v-1);
	}
}

const int N = 1069;
V<int> adj[N];
bool g[N][N];

int two[k];
int ori[N];

V<int> aadj[N];

void Bob(int ntot,int m,int u[],int v[]){

	int n = ntot-k-2;
	// dbg(n);
	rep(i,0,N){
		adj[i].clear();
		rep(j,0,N) g[i][j] = 0;
	}
	rep(i,0,m){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
		g[u[i]][v[i]] = g[v[i]][u[i]] = 1;

		// cout << u[i] _ v[i] << nl;
	}

	// dbg("BOB0");

	// find node with degree n+k
	int b = 0;
	while((int)adj[b].size()!=n+k) b++;
	rep(i,0,ntot) if(i!=b) assert((int)adj[i].size()!=n+k);
	// dbg(b);

	// dbg("BOB1");

	// find the node disconnected from b
	int a;
	rep(i,0,ntot) if(i!=b && !g[i][b]){
		a = i; break;
	}
	rep(i,0,ntot) if(i!=b && !g[i][b]) assert(i==a);
	assert(adj[a].size()==k);
	// dbg("BOB2");
	// dbg(a);

	// determine two[], take a subgraph
	V<int>&vec = adj[a];
	for(int x : vec){
		for(int y : adj[x]){
			bool ok = 0;
			for(int z : vec) ok |= y==z;
			if(ok){
				// cout << x _ y << nl;
				aadj[x].push_back(y);
			}
		}
	}

	int p;
	rep(i,0,k){
		p = adj[a][i];

		bool ok = 1;
		ok &= aadj[p].size()==2;
		if(!ok) continue;
		// dbg(i);
		// dbg(p);

		int q = aadj[p][0], r = aadj[p][1];
		// dbg(q); dbg(r);
		ok &= aadj[q].size()==3;
		ok &= aadj[r].size()==3;
		ok &= g[q][r];
		// dbg(ok);
		if(ok) break;
	}
	// dbg(p);
	// dbg(aadj[p].size());
	// cout << nl << nl;

	int q = aadj[p][0], r = aadj[p][1];
	bool ok = 0;
	for(int x : aadj[q]) if(x!=p && x!=r && g[a][x]){
		ok = aadj[x].size()==1;
	}
	if(!ok) swap(q, r);

	two[0] = p;
	two[2] = q;
	two[3] = r;
	for(int x : aadj[q]) if(x!=p && x!=r){
		two[1] = x;
	}

	// find the rest of two[]
	rep(i,4,k){
		for(int y : aadj[two[i-1]]) if(y!=two[i-2] && y!=two[i-4] && g[a][y]){
			two[i] = y;
		}
	}

	// dbg("BOB3");
	// rep(i,0,k) cout << i _ two[i] << nl;

	// recover nodes
	rep(i,0,ntot){
		// check importance
		bool flag = 0;
		flag |= i==a || i==b;
		rep(j,0,k) flag |= i==two[j];
		if(flag) continue;
		ori[i] = 0;

		// dbg(i);

		rep(j,0,k) if(g[i][two[j]]){
			ori[i] ^= 1<<j;
		}
	}
	// dbg("BOB4");

	// recover edges
	rep(i,0,m){
		// check importance
		bool flag = 0;
		flag = u[i]==a || u[i]==b || v[i]==a || v[i]==b;
		rep(j,0,k) flag |= u[i]==two[j] || v[i]==two[j];
		if(flag) continue;

		// cout << u[i] _ v[i] << nl;
		// cout << ori[u[i]] _ ori[v[i]] << nl;
		BobMake(ori[u[i]],ori[v[i]]);
	}

	BobFinish(n);
	return; InitMap(3,2); MakeMap(1,2); MakeMap(1,3);
}

Compilation message

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:176:29: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
  176 |   flag = u[i]==a || u[i]==b || v[i]==a || v[i]==b;
      |          ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5668 KB Output is correct
2 Correct 3 ms 5764 KB Output is correct
3 Correct 4 ms 5764 KB Output is correct
4 Correct 4 ms 5700 KB Output is correct
5 Correct 3 ms 5776 KB Output is correct
6 Correct 3 ms 5704 KB Output is correct
7 Correct 3 ms 5688 KB Output is correct
8 Correct 3 ms 5764 KB Output is correct
9 Correct 4 ms 5864 KB Output is correct
10 Correct 4 ms 5768 KB Output is correct
11 Correct 3 ms 5764 KB Output is correct
12 Correct 3 ms 5764 KB Output is correct
13 Correct 5 ms 5840 KB Output is correct
14 Correct 3 ms 5764 KB Output is correct
15 Correct 3 ms 5704 KB Output is correct
16 Correct 3 ms 5772 KB Output is correct
17 Correct 3 ms 5744 KB Output is correct
18 Correct 3 ms 5776 KB Output is correct
19 Correct 3 ms 5768 KB Output is correct
20 Correct 3 ms 5740 KB Output is correct
21 Correct 3 ms 5768 KB Output is correct
22 Correct 3 ms 5784 KB Output is correct
23 Correct 3 ms 5764 KB Output is correct
24 Correct 2 ms 5760 KB Output is correct
25 Correct 3 ms 5740 KB Output is correct
26 Correct 3 ms 5772 KB Output is correct
27 Correct 3 ms 5764 KB Output is correct
28 Correct 3 ms 5692 KB Output is correct
29 Correct 3 ms 5668 KB Output is correct
30 Correct 2 ms 5668 KB Output is correct
31 Correct 2 ms 5740 KB Output is correct
32 Correct 2 ms 5768 KB Output is correct
33 Correct 2 ms 5760 KB Output is correct
34 Correct 2 ms 5700 KB Output is correct
35 Correct 3 ms 5748 KB Output is correct
36 Correct 3 ms 5764 KB Output is correct
37 Correct 3 ms 5740 KB Output is correct
38 Correct 3 ms 5704 KB Output is correct
39 Correct 2 ms 5764 KB Output is correct
40 Correct 2 ms 5772 KB Output is correct
41 Correct 3 ms 5772 KB Output is correct
42 Correct 2 ms 5764 KB Output is correct
43 Correct 3 ms 5744 KB Output is correct
44 Correct 3 ms 5768 KB Output is correct
45 Correct 2 ms 5692 KB Output is correct
46 Correct 3 ms 5772 KB Output is correct
47 Correct 3 ms 5772 KB Output is correct
48 Correct 2 ms 5764 KB Output is correct
49 Correct 3 ms 5772 KB Output is correct
50 Correct 2 ms 5760 KB Output is correct
51 Correct 2 ms 5764 KB Output is correct
52 Correct 3 ms 5764 KB Output is correct
53 Correct 3 ms 5800 KB Output is correct
54 Correct 2 ms 5764 KB Output is correct
55 Correct 2 ms 5764 KB Output is correct
56 Correct 3 ms 5764 KB Output is correct
57 Correct 3 ms 5756 KB Output is correct
58 Correct 3 ms 5764 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5668 KB Output is correct
2 Correct 3 ms 5764 KB Output is correct
3 Correct 4 ms 5764 KB Output is correct
4 Correct 4 ms 5700 KB Output is correct
5 Correct 3 ms 5776 KB Output is correct
6 Correct 3 ms 5704 KB Output is correct
7 Correct 3 ms 5688 KB Output is correct
8 Correct 3 ms 5764 KB Output is correct
9 Correct 4 ms 5864 KB Output is correct
10 Correct 4 ms 5768 KB Output is correct
11 Correct 3 ms 5764 KB Output is correct
12 Correct 3 ms 5764 KB Output is correct
13 Correct 5 ms 5840 KB Output is correct
14 Correct 3 ms 5764 KB Output is correct
15 Correct 3 ms 5704 KB Output is correct
16 Correct 3 ms 5772 KB Output is correct
17 Correct 3 ms 5744 KB Output is correct
18 Correct 3 ms 5776 KB Output is correct
19 Correct 3 ms 5768 KB Output is correct
20 Correct 3 ms 5740 KB Output is correct
21 Correct 3 ms 5768 KB Output is correct
22 Correct 3 ms 5784 KB Output is correct
23 Correct 3 ms 5764 KB Output is correct
24 Correct 2 ms 5760 KB Output is correct
25 Correct 3 ms 5740 KB Output is correct
26 Correct 3 ms 5772 KB Output is correct
27 Correct 3 ms 5764 KB Output is correct
28 Correct 3 ms 5692 KB Output is correct
29 Correct 3 ms 5668 KB Output is correct
30 Correct 2 ms 5668 KB Output is correct
31 Correct 2 ms 5740 KB Output is correct
32 Correct 2 ms 5768 KB Output is correct
33 Correct 2 ms 5760 KB Output is correct
34 Correct 2 ms 5700 KB Output is correct
35 Correct 3 ms 5748 KB Output is correct
36 Correct 3 ms 5764 KB Output is correct
37 Correct 3 ms 5740 KB Output is correct
38 Correct 3 ms 5704 KB Output is correct
39 Correct 2 ms 5764 KB Output is correct
40 Correct 2 ms 5772 KB Output is correct
41 Correct 3 ms 5772 KB Output is correct
42 Correct 2 ms 5764 KB Output is correct
43 Correct 3 ms 5744 KB Output is correct
44 Correct 3 ms 5768 KB Output is correct
45 Correct 2 ms 5692 KB Output is correct
46 Correct 3 ms 5772 KB Output is correct
47 Correct 3 ms 5772 KB Output is correct
48 Correct 2 ms 5764 KB Output is correct
49 Correct 3 ms 5772 KB Output is correct
50 Correct 2 ms 5760 KB Output is correct
51 Correct 2 ms 5764 KB Output is correct
52 Correct 3 ms 5764 KB Output is correct
53 Correct 3 ms 5800 KB Output is correct
54 Correct 2 ms 5764 KB Output is correct
55 Correct 2 ms 5764 KB Output is correct
56 Correct 3 ms 5764 KB Output is correct
57 Correct 3 ms 5756 KB Output is correct
58 Correct 3 ms 5764 KB Output is correct
59 Correct 4 ms 6024 KB Output is correct
60 Correct 4 ms 5948 KB Output is correct
61 Correct 3 ms 5892 KB Output is correct
62 Correct 3 ms 5764 KB Output is correct
63 Correct 3 ms 5772 KB Output is correct
64 Correct 4 ms 6020 KB Output is correct
65 Correct 4 ms 5932 KB Output is correct
66 Correct 4 ms 5868 KB Output is correct
67 Correct 4 ms 5876 KB Output is correct
68 Correct 3 ms 5772 KB Output is correct
69 Correct 3 ms 5764 KB Output is correct
70 Correct 4 ms 5856 KB Output is correct
71 Correct 3 ms 6012 KB Output is correct
72 Correct 4 ms 6020 KB Output is correct
73 Correct 4 ms 5892 KB Output is correct
74 Correct 3 ms 5740 KB Output is correct
75 Correct 3 ms 5764 KB Output is correct
76 Correct 4 ms 5904 KB Output is correct
77 Correct 3 ms 6020 KB Output is correct
78 Correct 3 ms 6020 KB Output is correct
79 Correct 4 ms 5936 KB Output is correct
80 Correct 3 ms 5844 KB Output is correct
81 Correct 3 ms 5748 KB Output is correct
82 Correct 3 ms 5764 KB Output is correct
83 Correct 3 ms 5896 KB Output is correct
84 Correct 3 ms 5868 KB Output is correct
85 Correct 5 ms 5996 KB Output is correct
86 Correct 3 ms 5896 KB Output is correct
87 Correct 3 ms 5900 KB Output is correct
88 Correct 4 ms 5672 KB Output is correct
89 Correct 3 ms 5760 KB Output is correct
90 Correct 2 ms 5760 KB Output is correct
91 Correct 3 ms 5780 KB Output is correct
92 Correct 3 ms 5668 KB Output is correct
93 Correct 4 ms 5692 KB Output is correct
94 Correct 4 ms 6024 KB Output is correct
95 Correct 4 ms 6000 KB Output is correct
96 Correct 3 ms 6020 KB Output is correct
97 Correct 4 ms 5920 KB Output is correct
98 Correct 3 ms 6000 KB Output is correct
99 Correct 3 ms 5892 KB Output is correct
100 Correct 3 ms 5892 KB Output is correct
101 Correct 3 ms 5764 KB Output is correct
102 Correct 2 ms 5736 KB Output is correct
103 Correct 3 ms 5840 KB Output is correct
104 Correct 3 ms 5764 KB Output is correct
105 Correct 4 ms 5892 KB Output is correct
106 Correct 5 ms 5868 KB Output is correct
107 Correct 4 ms 5764 KB Output is correct
108 Correct 3 ms 5748 KB Output is correct
109 Correct 3 ms 6020 KB Output is correct
110 Correct 3 ms 5744 KB Output is correct
111 Correct 3 ms 5900 KB Output is correct
112 Correct 3 ms 5764 KB Output is correct
113 Correct 4 ms 5744 KB Output is correct
114 Correct 3 ms 5892 KB Output is correct
115 Correct 3 ms 5880 KB Output is correct
116 Correct 3 ms 5768 KB Output is correct
117 Correct 3 ms 5892 KB Output is correct
118 Correct 3 ms 5880 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Runtime error 641 ms 56948 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -