oj.uz

Submission #260818

# Submission time Handle Problem Language Result Execution time Memory
260818 2020-08-11T04:19:09 Z arnold518 Airline Route Map (JOI18_airline) C++14
0 / 100
 2500 ms 38520 KB 
#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
static int N, M, *A, *B;
static vector<pii> E;
 
void Alice(int _N, int _M, int _A[], int _B[])
{
	N=_N; M=_M; A=_A; B=_B;
 
	for(int i=0; i<M; i++)
	{
		int u=A[i]+1, v=B[i]+1;
		E.push_back({u, v});
	}
 
	for(int i=0; i<7; i++)
	{
		for(int j=1; j<=N; j++)
		{
			int now=j;
			for(int k=0; k<i; k++) now/=3;
			if(now%3==1) E.push_back({N+i+1, j});
			else if(now%3==2) E.push_back({j, N+i+1});
		}
	}
 
	for(int i=0; i<2; i++)
	{
		for(int j=1; j<=7; j++)
		{
			int now=j;
			for(int k=0; k<i; k++) now/=3;
			if(now%3==1) E.push_back({N+i+8, N+j});
			else if(now%3==2) E.push_back({N+j, N+i+8});
		}
	}
 
	E.push_back({N+10, N+8});
	E.push_back({N+9, N+10});
 
	for(int i=1; i<=N+9; i++)
	{
		E.push_back({0, i});
		E.push_back({N+11, i});
	}
	E.push_back({0, N+11});
 
	InitG(N+12, E.size());
	for(int i=0; i<E.size(); i++) MakeG(i, E[i].first, E[i].second);
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
static const int MAXN = 1100;
 
static int V, U, *C, *D;
static vector<int> adj[MAXN+10];
static vector<int> radj[MAXN+10];
static int N, deg[MAXN+10], A[MAXN+10], B[MAXN+10];
static vector<pii> E;
static bool vis[MAXN+10];
static const int POW[10] = {1, 3, 9, 27, 81, 243, 729};
 
void Bob(int _V, int _U, int _C[], int _D[])
{
	V=_V; U=_U; C=_C; D=_D; N=V-12;
	for(int i=0; i<U; i++)
	{
		int u=C[i], v=D[i];
		adj[u].push_back(v);
		radj[v].push_back(u);
		deg[u]++; deg[v]++;
	}
 
	int P, Q, R;
	for(int i=0; i<V; i++) if(deg[i]==2) { P=i; break; }
	for(int i=0; i<V; i++) if(deg[i]==N+10) vis[i]=1;
	Q=adj[P].front(); R=radj[P].front();
	assert(adj[P].size()==1); assert(radj[P].size()==1);
	vis[P]=1; vis[Q]=1; vis[R]=1;
 
	vector<int> VV;
	for(auto it : adj[Q])
	{
		if(vis[it]) continue;
		VV.push_back(it);
		A[it]+=1;
	}
	for(auto it : radj[Q])
	{
		if(vis[it]) continue;
		VV.push_back(it);
		A[it]+=2;
	}
	for(auto it : adj[R])
	{
		if(vis[it]) continue;
		VV.push_back(it);
		A[it]+=3;
	}
	for(auto it : radj[R])
	{
		if(vis[it]) continue;
		VV.push_back(it);
		A[it]+=6;
	}
	sort(VV.begin(), VV.end());
	VV.erase(unique(VV.begin(), VV.end()), VV.end());
 	if(VV.size()!=7) while(1);

	for(auto it : VV)
	{
		vis[it]=1;
		B[A[it]-1]=it;
	}
 
	VV.clear();
	for(int i=0; i<7; i++)
	{
		for(auto it : adj[B[i]])
		{
			if(vis[it]) continue;
			VV.push_back(it);
			A[it]+=POW[i];
		}
		for(auto it : radj[B[i]])
		{
			if(vis[it]) continue;
			VV.push_back(it);
			A[it]+=POW[i]*2;
		}
	}
 
	sort(VV.begin(), VV.end());
	VV.erase(unique(VV.begin(), VV.end()), VV.end());
	if(VV.size()!=N) while(1);

	vector<int> VVV;
	for(auto it : VV) VVV.push_back(A[it]);
	sort(VVV.begin(), VVV.end());
	for(int i=0; i<VVV.size(); i++) if(VVV[i]!=i+1) while(1);
 
	for(auto now : VV)
	{
		for(auto nxt : adj[now])
		{
			if(vis[nxt]) continue;
			E.push_back({A[now], A[nxt]});
		}
	}
 
	InitMap(N, E.size());
	for(auto it : E) MakeMap(it.first-1, it.second-1);
}

Compilation message

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:55:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<E.size(); i++) MakeG(i, E[i].first, E[i].second);
               ~^~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:91:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(VV.size()!=N) while(1);
     ~~~~~~~~~^~~
Bob.cpp:96:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<VVV.size(); i++) if(VVV[i]!=i+1) while(1);
               ~^~~~~~~~~~~
Bob.cpp:30:6: warning: 'P' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int P, Q, R;
      ^

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3040 ms 6912 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3040 ms 6912 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Runtime error 713 ms 38520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -