QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#853208 | #9726. AUS | ucup-team296# | RE | 0ms | 2104kb | Rust | 16.0kb | 2025-01-11 16:09:53 | 2025-01-11 16:09:55 |
Judging History
answer
// https://contest.ucup.ac/contest/1893/problem/9726
pub mod solution {
//{"name":"A. AUS","group":"Universal Cup - The 3rd Universal Cup. Stage 25: Hangzhou","url":"https://contest.ucup.ac/contest/1893/problem/9726","interactive":false,"timeLimit":1000,"tests":[{"input":"4\nabab\ncdcd\nabce\nabab\ncdcd\nabcd\nabab\ncdcd\nabc\nx\nyz\ndef\n","output":"YES\nNO\nYES\nNO\n"}],"testType":"single","input":{"type":"stdin","fileName":null,"pattern":null},"output":{"type":"stdout","fileName":null,"pattern":null},"languages":{"java":{"taskClass":"AAUS"}}}
#[allow(unused)]
use crate::dbg;
use crate::algo_lib::graph::dsu::Dsu;
use crate::algo_lib::io::input::Input;
use crate::algo_lib::io::output::Output;
fn solve(input: &mut Input, out: &mut Output, _test_case: usize) {
let tc = input.usize();
for _ in 0..tc {
let s1 = input.string();
let s2 = input.string();
let s3 = input.string();
let mut ok = s1.len() == s2.len();
let mut dsu = Dsu::new(26);
for i in 0..s1.len() {
let p1 = s1[i] as usize - 'a' as usize;
let p2 = s2[i] as usize - 'a' as usize;
dsu.unite(p1, p2);
}
if s1.len() == s3.len() {
ok = false;
for i in 0..s1.len() {
let p1 = s1[i] as usize - 'a' as usize;
let p2 = s3[i] as usize - 'a' as usize;
if dsu.get(p1) != dsu.get(p2) {
ok = true;
}
}
}
if ok {
out.println("YES");
} else {
out.println("NO");
}
}
}
pub(crate) fn run(mut input: Input, mut output: Output) -> bool {
solve(&mut input, &mut output, 1);
output.flush();
true
}
}
pub mod algo_lib {
#![feature(test)]
#![allow(clippy::too_many_arguments)]
#![allow(clippy::type_complexity)]
pub mod graph {
pub mod dsu {
pub struct Dsu {
p: Vec<u32>,
size: Vec<u32>,
num_comps: u32,
}
impl Dsu {
pub fn clear(&mut self) {
for (idx, val) in self.p.iter_mut().enumerate() {
*val = idx as u32;
}
for val in self.size.iter_mut() {
*val = 1;
}
self.num_comps = self.p.len() as u32;
}
pub fn new(n: usize) -> Self {
let mut res = Self {
p: vec![0; n],
size: vec![0; n],
num_comps: n as u32,
};
res.clear();
res
}
pub fn get(&mut self, v: usize) -> usize {
if self.p[v] as usize != v {
self.p[v] = self.get(self.p[v] as usize) as u32;
}
self.p[v] as usize
}
pub fn unite(&mut self, v1: usize, v2: usize) -> bool {
let v1 = self.get(v1);
let v2 = self.get(v2);
if v1 == v2 {
false
} else {
self.p[v1] = v2 as u32;
self.size[v2] += self.size[v1];
self.num_comps -= 1;
true
}
}
pub fn calc_size(&mut self, mut v: usize) -> usize {
v = self.get(v);
self.size[v] as usize
}
pub fn is_root(&self, v: usize) -> bool {
self.p[v] as usize == v
}
pub fn calc_components(&mut self) -> Vec<Vec<usize>> {
let n = self.p.len();
let mut res = vec![vec![]; n];
for v in 0..n {
res[self.get(v)].push(v);
}
res.into_iter().filter(|vec| !vec.is_empty()).collect()
}
pub fn num_components(&self) -> usize {
self.num_comps as usize
}
pub fn len(&self) -> usize {
self.p.len()
}
}
}
}
pub mod io {
pub mod input {
use std::fmt::Debug;
use std::io::Read;
use std::marker::PhantomData;
use std::path::Path;
use std::str::FromStr;
pub struct Input {
input: Box<dyn Read>,
buf: Vec<u8>,
at: usize,
buf_read: usize,
}
macro_rules! read_integer_fun {
($t:ident) => {
#[allow(unused)]
pub fn $t(&mut self) -> $t {
self.read_integer()
}
};
}
impl Input {
const DEFAULT_BUF_SIZE: usize = 4096;
///
/// Using with stdin:
/// ```no_run
/// use algo_lib::io::input::Input;
/// let stdin = std::io::stdin();
/// let input = Input::new(Box::new(stdin));
/// ```
///
/// For read files use ``new_file`` instead.
///
///
pub fn new(input: Box<dyn Read>) -> Self {
Self {
input,
buf: vec![0; Self::DEFAULT_BUF_SIZE],
at: 0,
buf_read: 0,
}
}
pub fn new_stdin() -> Self {
let stdin = std::io::stdin();
Self::new(Box::new(stdin))
}
pub fn new_file<P: AsRef<Path>>(path: P) -> Self {
let file = std::fs::File::open(&path)
.unwrap_or_else(|_| panic!("Can't open file: {:?}", path.as_ref().as_os_str()));
Self::new(Box::new(file))
}
pub fn new_with_size(input: Box<dyn Read>, buf_size: usize) -> Self {
Self {
input,
buf: vec![0; buf_size],
at: 0,
buf_read: 0,
}
}
pub fn new_file_with_size<P: AsRef<Path>>(path: P, buf_size: usize) -> Self {
let file = std::fs::File::open(&path)
.unwrap_or_else(|_| panic!("Can't open file: {:?}", path.as_ref().as_os_str()));
Self::new_with_size(Box::new(file), buf_size)
}
pub fn get(&mut self) -> Option<u8> {
if self.refill_buffer() {
let res = self.buf[self.at];
self.at += 1;
Some(res)
} else {
None
}
}
pub fn peek(&mut self) -> Option<u8> {
if self.refill_buffer() {
Some(self.buf[self.at])
} else {
None
}
}
pub fn skip_whitespace(&mut self) {
while let Some(b) = self.peek() {
if !char::from(b).is_whitespace() {
return;
}
self.get();
}
}
pub fn next_token(&mut self) -> Option<Vec<u8>> {
self.skip_whitespace();
let mut res = Vec::new();
while let Some(c) = self.get() {
if char::from(c).is_whitespace() {
break;
}
res.push(c);
}
if res.is_empty() {
None
} else {
Some(res)
}
}
//noinspection RsSelfConvention
pub fn is_exhausted(&mut self) -> bool {
self.peek().is_none()
}
pub fn has_more_elements(&mut self) -> bool {
!self.is_exhausted()
}
pub fn read<T: Readable>(&mut self) -> T {
T::read(self)
}
pub fn vec<T: Readable>(&mut self, size: usize) -> Vec<T> {
let mut res = Vec::with_capacity(size);
for _ in 0usize..size {
res.push(self.read());
}
res
}
pub fn string_vec(&mut self, size: usize) -> Vec<Vec<u8>> {
let mut res = Vec::with_capacity(size);
for _ in 0usize..size {
res.push(self.string());
}
res
}
pub fn read_line(&mut self) -> String {
let mut res = String::new();
while let Some(c) = self.get() {
if c == b'\n' {
break;
}
if c == b'\r' {
if self.peek() == Some(b'\n') {
self.get();
}
break;
}
res.push(c.into());
}
res
}
#[allow(clippy::should_implement_trait)]
pub fn into_iter<T: Readable>(self) -> InputIterator<T> {
InputIterator {
input: self,
phantom: Default::default(),
}
}
fn read_integer<T: FromStr + Debug>(&mut self) -> T
where
<T as FromStr>::Err: Debug,
{
let res = self.read_string();
res.parse::<T>().unwrap()
}
fn read_string(&mut self) -> String {
match self.next_token() {
None => {
panic!("Input exhausted");
}
Some(res) => unsafe { String::from_utf8_unchecked(res) },
}
}
pub fn string_as_string(&mut self) -> String {
self.read_string()
}
pub fn string(&mut self) -> Vec<u8> {
self.read_string().into_bytes()
}
fn read_char(&mut self) -> char {
self.skip_whitespace();
self.get().unwrap().into()
}
fn read_float(&mut self) -> f64 {
self.read_string().parse().unwrap()
}
pub fn f64(&mut self) -> f64 {
self.read_float()
}
fn refill_buffer(&mut self) -> bool {
if self.at == self.buf_read {
self.at = 0;
self.buf_read = self.input.read(&mut self.buf).unwrap();
self.buf_read != 0
} else {
true
}
}
read_integer_fun!(i32);
read_integer_fun!(i64);
read_integer_fun!(i128);
read_integer_fun!(u32);
read_integer_fun!(u64);
read_integer_fun!(usize);
}
pub trait Readable {
fn read(input: &mut Input) -> Self;
}
impl Readable for String {
fn read(input: &mut Input) -> Self {
input.read_string()
}
}
impl Readable for char {
fn read(input: &mut Input) -> Self {
input.read_char()
}
}
impl Readable for f64 {
fn read(input: &mut Input) -> Self {
input.read_string().parse().unwrap()
}
}
impl Readable for f32 {
fn read(input: &mut Input) -> Self {
input.read_string().parse().unwrap()
}
}
impl<T: Readable> Readable for Vec<T> {
fn read(input: &mut Input) -> Self {
let size = input.read();
input.vec(size)
}
}
pub struct InputIterator<T: Readable> {
input: Input,
phantom: PhantomData<T>,
}
impl<T: Readable> Iterator for InputIterator<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
self.input.skip_whitespace();
self.input.peek().map(|_| self.input.read())
}
}
macro_rules! read_integer {
($t:ident) => {
impl Readable for $t {
fn read(input: &mut Input) -> Self {
input.read_integer()
}
}
};
}
read_integer!(i8);
read_integer!(i16);
read_integer!(i32);
read_integer!(i64);
read_integer!(i128);
read_integer!(isize);
read_integer!(u8);
read_integer!(u16);
read_integer!(u32);
read_integer!(u64);
read_integer!(u128);
read_integer!(usize);
}
pub mod output {
use std::io::Write;
pub struct Output {
output: Box<dyn Write>,
buf: Vec<u8>,
at: usize,
auto_flush: bool,
}
impl Output {
const DEFAULT_BUF_SIZE: usize = 4096;
pub fn new(output: Box<dyn Write>) -> Self {
Self {
output,
buf: vec![0; Self::DEFAULT_BUF_SIZE],
at: 0,
auto_flush: false,
}
}
pub fn new_stdout() -> Self {
let stdout = std::io::stdout();
Self::new(Box::new(stdout))
}
pub fn new_file(path: impl AsRef<std::path::Path>) -> Self {
let file = std::fs::File::create(path).unwrap();
Self::new(Box::new(file))
}
pub fn new_with_auto_flush(output: Box<dyn Write>) -> Self {
Self {
output,
buf: vec![0; Self::DEFAULT_BUF_SIZE],
at: 0,
auto_flush: true,
}
}
pub fn flush(&mut self) {
if self.at != 0 {
self.output.write_all(&self.buf[..self.at]).unwrap();
self.at = 0;
self.output.flush().expect("Couldn't flush output");
}
}
pub fn print<T: Writable>(&mut self, s: T) {
s.write(self);
}
pub fn println<T: Writable>(&mut self, s: T) {
s.write(self);
self.put(b'\n');
}
pub fn put(&mut self, b: u8) {
self.buf[self.at] = b;
self.at += 1;
if self.at == self.buf.len() {
self.flush();
}
}
pub fn maybe_flush(&mut self) {
if self.auto_flush {
self.flush();
}
}
pub fn print_per_line<T: Writable>(&mut self, arg: &[T]) {
for i in arg {
i.write(self);
self.put(b'\n');
}
}
pub fn print_iter<T: Writable, I: Iterator<Item = T>>(&mut self, iter: I) {
let mut first = true;
for e in iter {
if first {
first = false;
} else {
self.put(b' ');
}
e.write(self);
}
}
pub fn print_iter_ref<'a, T: 'a + Writable, I: Iterator<Item = &'a T>>(&mut self, iter: I) {
let mut first = true;
for e in iter {
if first {
first = false;
} else {
self.put(b' ');
}
e.write(self);
}
}
}
impl Write for Output {
fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
let mut start = 0usize;
let mut rem = buf.len();
while rem > 0 {
let len = (self.buf.len() - self.at).min(rem);
self.buf[self.at..self.at + len].copy_from_slice(&buf[start..start + len]);
self.at += len;
if self.at == self.buf.len() {
self.flush();
}
start += len;
rem -= len;
}
if self.auto_flush {
self.flush();
}
Ok(buf.len())
}
fn flush(&mut self) -> std::io::Result<()> {
self.flush();
Ok(())
}
}
pub trait Writable {
fn write(&self, output: &mut Output);
}
impl Writable for &str {
fn write(&self, output: &mut Output) {
output.write_all(self.as_bytes()).unwrap();
}
}
impl Writable for String {
fn write(&self, output: &mut Output) {
output.write_all(self.as_bytes()).unwrap();
}
}
impl Writable for char {
fn write(&self, output: &mut Output) {
output.put(*self as u8);
}
}
impl<T: Writable> Writable for [T] {
fn write(&self, output: &mut Output) {
output.print_iter_ref(self.iter());
}
}
impl<T: Writable> Writable for Vec<T> {
fn write(&self, output: &mut Output) {
self[..].write(output);
}
}
macro_rules! write_to_string {
($t:ident) => {
impl Writable for $t {
fn write(&self, output: &mut Output) {
self.to_string().write(output);
}
}
};
}
write_to_string!(u8);
write_to_string!(u16);
write_to_string!(u32);
write_to_string!(u64);
write_to_string!(u128);
write_to_string!(usize);
write_to_string!(i8);
write_to_string!(i16);
write_to_string!(i32);
write_to_string!(i64);
write_to_string!(i128);
write_to_string!(isize);
write_to_string!(f32);
write_to_string!(f64);
impl<T: Writable, U: Writable> Writable for (T, U) {
fn write(&self, output: &mut Output) {
self.0.write(output);
output.put(b' ');
self.1.write(output);
}
}
impl<T: Writable, U: Writable, V: Writable> Writable for (T, U, V) {
fn write(&self, output: &mut Output) {
self.0.write(output);
output.put(b' ');
self.1.write(output);
output.put(b' ');
self.2.write(output);
}
}
}
}
pub mod misc {
pub mod dbg_macro {
#[macro_export]
#[allow(unused_macros)]
macro_rules! dbg {
($first_val:expr, $($val:expr),+ $(,)?) => {
eprint!("[{}:{}] {} = {:?}",
file!(), line!(), stringify!($first_val), &$first_val);
($(eprint!(", {} = {:?}", stringify!($val), &$val)),+,);
eprintln!();
};
($first_val:expr) => {
eprintln!("[{}:{}] {} = {:?}",
file!(), line!(), stringify!($first_val), &$first_val)
};
}
}
}
}
fn main() {
let input = algo_lib::io::input::Input::new_stdin();
let mut output = algo_lib::io::output::Output::new_stdout();
crate::solution::run(input, output);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 2104kb
input:
4 abab cdcd abce abab cdcd abcd abab cdcd abc x yz def
output:
YES NO YES NO
result:
ok 4 lines
Test #2:
score: -100
Runtime Error
input:
10 ekkzjwextuoazxsosiiiditwrjiztfvxtzaztmdfhxroaqkjcdgsgiitkfglcrtgjquspjyjtodyhxetldbhvxampcvbinzgksxkunduhvbddakqswurshbnuazthfnxmsuyypznmxmatsnvpqovscnkkcjphtcmcsqteeikwggnugskjjwttvlrxmmrkyltxjhfiqicttcfumurdrmiqauruywgdomxxpbeunliyvsutrneexoyckjflhnmmaaovxubnptlemptxbhrflbnfcowktydgbugdxvkvegza...