제출 #1222615

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222615		PenguinsAreCute	항공 노선도 (JOI18_airline)	C++17	91 / 100	168 ms	23256 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
void Alice( int N, int M, int A[], int B[] ){
	vector<pair<int,int>> edge;
	int realN = N;
	if(!(N & 1))
		N++;
	int deg[N+12];
	memset(deg,0,sizeof(deg));
	for(int i=0;i<M;i++) {
		edge.push_back({A[i],B[i]});
		deg[A[i]] ^= 1;
		deg[B[i]] ^= 1;
	}
	for(int i=0;i<10;i++) {
		int cnt = 0;
		for(int j=0;j<N;j++)
			cnt += !!((1 << i) & (j % realN));
		if(cnt & 1) {
			for(int j=0;j<N;j++)
				if(!!((1<<i)&(j % realN))) {
					deg[N+i] ^= 1;
					deg[j] ^= 1;
					edge.push_back({N+i,j});
				}
		} else
			for(int j=0;j<N;j++)
				if(!((1<<i)&(j % realN))) {
					deg[N+i] ^= 1;
					deg[j] ^= 1;
					edge.push_back({N+i,j});
				}
	}
	for(int i=0;i<N;i++)
		if(deg[i]) {
			edge.push_back({i,N+10});
			deg[N+10] ^= 1;
			deg[i] ^= 1;
		}
	for(int i=0;i<12;i++)
		cerr << deg[N+i] << " \n"[i==11];
	for(int i=0;i<9;i++)
		edge.push_back({N+i,N+i+1});
	edge.push_back({N+10,N});
	edge.push_back({N+9,N+11});
	edge.push_back({N+10,N+1});
	edge.push_back({N+1,N+3});
	edge.push_back({N+3,N+10});
	InitG(N+12, edge.size());
	for(int i=-1; auto [a, b]: edge)
		MakeG(++i, a, b);
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;

void Bob( int V, int U, int C[], int D[] ){
	int N = V - 12;
	int olddeg[V];
	vector<int> adj[V];
	memset(olddeg,0,sizeof(olddeg));
	for(int i=0;i<U;i++) {
		olddeg[C[i]] ^= 1;
		olddeg[D[i]] ^= 1;
		adj[C[i]].push_back(D[i]);
		adj[D[i]].push_back(C[i]);
	}
	int label[V];
	memset(label,0,sizeof(label));
	int newdeg[V];
	memset(newdeg,0,sizeof(newdeg));
	for(int i=0;i<V;i++)
		if(olddeg[i])
			for(auto j: adj[i])
				if(olddeg[j])
					newdeg[i]++;
	for(int i=0;i<V;i++)
		if(newdeg[i] == 1) {
			label[i] = N + 11;
			for(int c=1;c<8;c++) {
				for(auto j: adj[i])
					if(label[j] == 0 && olddeg[j]) {
						i = j;
						break;
					}
				label[i] = N + 10 - c;
			}
			for(int j=0;j<V;j++)
				if(newdeg[j] == 3)
					label[j] = N + 10;
				else if(newdeg[j] == 4 && label[j] == 0)
					label[j] = N + 1;
			for(int j=0;j<V;j++)
				if(newdeg[j] == 2 && label[j] == 0) {
					for(auto k: adj[j])
						if(label[k] == N + 10)
							label[j] = N;
					if(!label[j])
						label[j] = N + 2;
				}
			for(int j=0;j<V;j++)
				if(label[j] >= N && label[j] < N + 10) {
					int cnt = 0;
					for(auto k: adj[j])
						if(!olddeg[k])
							cnt++;
					if(cnt * 2 > N) {
						for(int k=0;k<V;k++)
							if(!olddeg[k])
								label[k] |= (1 << (label[j] - N));
						for(auto k: adj[j])
							if(!olddeg[k])
								label[k] &= ~(1 << (label[j] - N));
					} else {
						for(auto k: adj[j])
							if(!olddeg[k])
								label[k] |= (1 << (label[j] - N));
					}
				}
			int fnd = 0;
			for(int j=0;j<V;j++)
				if(label[j] == N - 1)
					fnd = 1;
			vector<pair<int,int>> edge;
			for(int j=0;j<V;j++)
				for(auto k: adj[j])
					if(label[j] < label[k] && label[k] < N)
						edge.push_back({label[j],label[k]});
			InitMap(N - 1 + fnd,edge.size());
			for(auto [j, k]: edge)
				MakeMap(j, k);
			return;
		}
}

컴파일 시 표준 에러 (stderr) 메시지

# 1번째 컴파일 단계

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:51:23: warning: range-based 'for' loops with initializer only available with '-std=c++20' or '-std=gnu++20'
   51 |         for(int i=-1; auto [a, b]: edge)
      |                       ^~~~

• Subtask 1: 22 / 22
• Subtask 2: 15 / 15
• Subtask 3: 54 / 63