結果
| 問題 |
No.2820 Non-Preferred IUPAC Nomenclature
|
| コンテスト | |
| ユーザー |
 ゆうき
|
| 提出日時 | 2024-07-26 22:29:02 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 1,288 ms / 2,000 ms |
| コード長 | 18,185 bytes |
| コンパイル時間 | 5,686 ms |
| コンパイル使用メモリ | 95,584 KB |
| 実行使用メモリ | 175,960 KB |
| 最終ジャッジ日時 | 2024-07-26 22:29:21 |
| 合計ジャッジ時間 | 16,512 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 22 |
ソースコード
import static java.lang.Math.*;
import static java.util.Arrays.*;
import java.io.*;
import java.lang.reflect.*;
import java.util.*;
import java.util.ArrayList;
import java.util.concurrent.*;
import java.util.function.*;
public final class Main{
public static void main(String[] args) throws Exception{
MyReader in = new MyReader(System.in);
MyWriter out = new MyWriter(System.out,false),log = new MyWriter(System.err,true);
int T = Solver.multi ? in.it() : 1;
while (T-- > 0)
Optional.ofNullable(new Solver(in,out,log).solve()).ifPresent(out::println);
out.flush();
}
}
class Solver extends BaseSolver{
public Solver(MyReader in,MyWriter out,MyWriter log){ super(in,out,log); }
public static boolean multi = false;
public Object solve(){
int N = in.it();
Graph<Long> g = new Graph<>(N,true);
for (int i = 0;i < N;i++)
for (int j = 0;j < 4;j++) {
String s = in.str();
if ("H".equals(s))
continue;
g.addEdge(i,Integer.parseInt(s) -1);
}
Deque<Character> dq = new ArrayDeque<>();
dfs(0,-1,g,dq);
StringBuilder ans = new StringBuilder();
for (var c:dq)
ans.append(c);
return ans.toString();
// int X = in.it(),Y = in.it();
//
// out.println(6);
// out.printlns(X,Y,X,Y,X,Y);
// out.flush();
//
// return in.it();
}
char[] a = "methane".toCharArray();
private void dfs(int u,int p,Graph<Long> g,Deque<Character> dq){
for (var e:g.go(u)) {
if (e.v == p)
continue;
dq.add('(');
dfs(e.v,u,g,dq);
dq.pollLast();
dq.pollLast();
dq.pollLast();
dq.add('y');
dq.add('l');
dq.add(')');
}
for (var c:a)
dq.add(c);
}
public int lis(int[] arr){
int[] lis = new int[arr.length];
fill(lis,infI);
for (var a:arr) {
int i = bSearchI(0,arr.length,ii -> lis[ii] < a) +1;
lis[i] = a;
}
return bSearchI(0,arr.length,i -> lis[i] < infI) +1;
}
long[] extend_gcd(long a,long b,long x,long y){
if (b == 0)
return new long[]{1, 0, a};
else {
long[] d = extend_gcd(b,a %b,y,x);
d[0] ^= d[1];
d[1] ^= d[0];
d[0] ^= d[1];
d[1] -= a /b *d[0];
return d;
}
}
}
class Data extends BaseV{}
class Permutation{
private int n;
int[] arr;
public Permutation(int n){ arr = Util.arrI(this.n = n,i -> i); }
public Permutation(int[] arr){ this.arr = copyOf(arr,n = arr.length); }
public boolean increment(){ return crement(1); }
public boolean decrement(){ return crement(-1); }
private boolean crement(int d){
int l = n -2;
while (0 <= l && arr[l] *d >= arr[l +1] *d)
l--;
if (l < 0)
return false;
int r = n -1;
while (arr[l] *d >= arr[r] *d)
r--;
swap(l,r);
l++;
r = n -1;
while (l < r)
swap(l++,r--);
return true;
}
private void swap(int l,int r){
arr[l] ^= arr[r];
arr[r] ^= arr[l];
arr[l] ^= arr[r];
}
}
class LowLink extends Graph<Long>{
private int[] low;
private int[] ord;
private int[] inc;
public LowLink(int n){ super(n,false); }
public void build(){
@SuppressWarnings("unchecked")
Iterator<Edge<Long>>[] iterator = new Iterator[n];
for (int v = 0;v < n;v++)
iterator[v] = go(v).iterator();
low = new int[n];
ord = new int[n];
fill(ord,-1);
inc = new int[n];
int[] stack = new int[n +2];
stack[0] = -1;
int len = 0;
int count = 0;
for (int root = 0;root < n;root++) {
if (ord[root] != -1)
continue;
ord[root] = low[root] = count++;
inc[root]--;
stack[len = 1] = root;
while (0 < len) {
int v = stack[len];
int p = stack[len -1];
if (iterator[v].hasNext()) {
int w = iterator[v].next().v;
if (ord[w] == -1) {
ord[w] = low[w] = count++;
stack[++len] = w;
} else if (w != p && low[v] > ord[w])
low[v] = ord[w];
} else {
len--;
if (p != -1) {
if (low[p] > low[v])
low[p] = low[v];
if (ord[p] <= low[v])
inc[p]++;
}
}
}
}
}
public boolean isBridge(int x,int y){ return ord[x] < low[y] || ord[y] < low[x]; }
public boolean isArticulation(int x){ return inc[x] > 0; }
public int articulationValue(int x){ return inc[x]; }
}
class Edge<L> {
public int id,u,v;
public L val;
public Edge<L> re;
public Edge(int id,int u,int v,L val){
this.id = id;
this.u = u;
this.v = v;
this.val = val;
}
}
class Graph<L> {
public int n;
public MyList<Edge<L>> es;
private MyList<Edge<L>>[] go,bk;
public Graph(int n,boolean dir){
this.n = n;
go = Util.cast(new MyList[n]);
bk = dir ? Util.cast(new MyList[n]) : go;
for (int i = 0;i < n;i++) {
go[i] = new MyList<>();
bk[i] = new MyList<>();
}
es = new MyList<>();
}
protected L inv(L l){ return l; }
public void addEdge(int u,int v){ addEdge(u,v,null); }
public void addEdge(int u,int v,L l){
var e = new Edge<>(es.size(),u,v,l);
var re = new Edge<>(e.id,e.v,e.u,inv(e.val));
es.add(e);
go[u].add(re.re = e);
bk[v].add(e.re = re);
}
public MyList<Edge<L>> go(int u){ return go[u]; }
public MyList<Edge<L>> bk(int u){ return bk[u]; }
}
class UnionFind{
int num;
protected int[] dat;
protected int[] nxt;
public UnionFind(int n){
dat = new int[n];
nxt = new int[n];
setAll(nxt,i -> i);
fill(dat,-1);
num = n;
}
public int root(int x){ return dat[x] < 0 ? x : (dat[x] = root(dat[x])); }
public boolean same(int u,int v){ return root(u) == root(v); }
public boolean unite(int u,int v){
if ((u = root(u)) == (v = root(v)))
return false;
if (dat[u] > dat[v]) {
u ^= v;
v ^= u;
u ^= v;
}
dat[u] += dat[v];
dat[v] = u;
num--;
nxt[u] ^= nxt[v];
nxt[v] ^= nxt[u];
nxt[u] ^= nxt[v];
return true;
}
public int size(int x){ return -dat[root(x)]; }
public int[] getGroup(int x){
int[] ret = new int[size(x)];
for (int i = 0,c = root(x);i < ret.length;i++)
ret[i] = c = nxt[c];
return ret;
}
}
class AVLTree{
private Node root;
public void add(long v){ add(v,1); }
public void add(long v,int k){ root = root == null ? new Node(v,k) : add(root,v,k); }
private Node add(Node nd,long v,int k){
if (nd.lft == null) {
int c = Long.compare(nd.val,v);
if (c == 0) {
nd.sz += k;
return nd;
} else {
var ret = new Node(0,0);
ret.cld(-c,new Node(v,k));
ret.cld(c,nd);
nd = ret;
}
} else {
int c = Long.compare(v,nd.rht.l);
nd.lft = c < 0 ? add(nd.lft,v,k) : nd.lft;
nd.rht = c < 0 ? nd.rht : add(nd.rht,v,k);
}
return balance(nd);
}
public void del(long v){ del(v,1); }
public void del(long v,int k){ root = del(root,v,k); }
private Node del(Node nd,long v,int k){
if (nd.lft == null) {
int c = Long.compare(nd.val,v);
if (c == 0)
nd.sz -= k;
return c != 0 || 0 < nd.sz ? nd : null;
}
int c = Long.compare(v,nd.rht.l) *2 +1;
Node del = del(c < 0 ? nd.lft : nd.rht,v,k);
if (del == null)
return nd.cld(-c);
nd.cld(c,del);
return balance(nd);
}
public long get(int i){ return get(root,i); }
private long get(Node nd,int i){
return nd.lft == null ? nd.val : i < nd.lft.sz ? get(nd.lft,i) : get(nd.rht,i -nd.lft.sz);
}
public long get(int l,int r){ return root == null ? 0 : get(root,l,min(r,size())); }
private long get(Node nd,int l,int r){
if (0 == l && r == nd.sz)
return nd.val();
else if (nd.lft == null)
return nd.val *(r -l);
else {
long ret = 0;
if (l < nd.lft.sz)
ret += get(nd.lft,l,min(nd.lft.sz,r));
if (nd.lft.sz < r)
ret += get(nd.rht,max(0,l -nd.lft.sz),r -nd.lft.sz);
return ret;
}
}
public long getUnder(long v){ return root == null || v < root.l ? 0 : getUnder(root,v); }
private long getUnder(Node nd,long v){
if (nd.lft == null)
return v <= nd.val ? 0 : nd.val();
return v < nd.rht.l ? getUnder(nd.lft,v) : nd.lft.val() +getUnder(nd.rht,v);
}
public int idx(long v){ return root == null || v < root.l ? 0 : idx(root,v); }
private int idx(Node nd,long v){
if (nd.lft == null)
return v <= nd.val ? 0 : nd.sz;
return v < nd.rht.l ? idx(nd.lft,v) : nd.lft.sz +idx(nd.rht,v);
}
public int size(){ return root == null ? 0 : root.sz; }
private Node balance(Node nd){ return (1 < abs(nd.bis = nd.rht.rnk -nd.lft.rnk) ? (nd = rotate(nd)) : nd).update(); }
private Node rotate(Node u){
var v = u.cld(u.bis);
if (u.bis *v.bis < -1)
v = rotate(v);
u.cld(u.bis,v.cld(-u.bis));
v.cld(-u.bis,u);
u.update();
return v;
}
private class Node{
private int sz,bis,rnk;
private long val,l;
private Node lft,rht;
private Node(long val,int sz){
this.sz = sz;
this.val = l = val;
}
private Node update(){
sz = lft.sz +rht.sz;
bis = rht.rnk -lft.rnk;
rnk = max(lft.rnk,rht.rnk) +1;
val = lft.val() +rht.val();
l = lft.l;
return this;
}
private Node cld(int c){ return c < 0 ? lft : rht; }
private void cld(int c,Node nd){ nd = c < 0 ? (lft = nd) : (rht = nd); }
private long val(){ return lft == null && 1 < sz ? val *sz : val; }
}
@Override
public String toString(){
List<Long> list = new ArrayList<>();
for (int i = 0;i < size();i++)
list.add(get(i));
return Arrays.toString(list.stream().mapToLong(z -> z).toArray());
}
}
abstract class BaseV{
public int sz;
public boolean fail;
}
class MyStack<T> extends MyList<T>{
public T pop(){ return remove(size() -1); }
public T peek(){ return get(size() -1); }
}
class MyList<T> implements Iterable<T>{
private T[] arr;
private int sz;
public MyList(){ this(16); }
public MyList(int n){ arr = Util.cast(new Object[max(16,n)]); }
public MyList(MyList<T> org){
this(org.sz);
System.arraycopy(org.arr,0,arr,0,sz = org.sz);
}
public boolean isEmpty(){ return sz == 0; }
public int size(){ return sz; }
public T get(int i){ return arr[i]; }
public void add(T t){ (arr = sz < arr.length ? arr : copyOf(arr,sz *5 >>2))[sz++] = t; }
public T remove(int i){
var ret = arr[i];
sz--;
for (int j = i;j < sz;j++)
arr[j] = arr[j +1];
return ret;
}
public T removeFast(int i){
var ret = arr[i];
arr[i] = arr[--sz];
return ret;
}
public void sort(){ sort(Util.cast(Comparator.naturalOrder())); }
public void sort(Comparator<T> cmp){ Arrays.sort(arr,0,sz,cmp); }
public <U> MyList<U> map(Function<T, U> func){
MyList<U> ret = new MyList<>(sz);
forEach(t -> ret.add(func.apply(t)));
return ret;
}
public MyList<T> rev(){
MyList<T> ret = new MyList<>(sz);
for (int i = sz;i-- > 0;)
ret.add(get(i));
return ret;
}
public T[] toArray(){ return copyOf(arr,sz); }
public void swap(int i,int j){
var t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public void set(int i,T t){ arr[i] = t; }
public void clear(){ sz = 0; }
@Override
public Iterator<T> iterator(){
return new Iterator<>(){
int i = 0;
@Override
public boolean hasNext(){ return i < sz; }
@Override
public T next(){ return arr[i++]; }
};
}
}
class BaseSolver extends Util{
public MyReader in;
public MyWriter out,log;
public BaseSolver(MyReader in,MyWriter out,MyWriter log){
this.in = in;
this.out = out;
this.log = log;
}
protected int[][] addId(int[][] T){
return arr(new int[T.length][],i -> {
int[] t = copyOf(T[i],T[i].length +1);
t[t.length -1] = i;
return t;
});
}
protected long inv(long x){ return pow(x,mod -2); }
protected long pow(long x,long n){ return pow(x,n,Util.mod); }
protected long pow(long x,long n,long mod){
long ret = 1;
for (x %= mod;0 < n;x = x *x %mod,n >>= 1)
if ((n &1) == 1)
ret = ret *x %mod;
return ret;
}
protected int bSearchI(int o,int n,IntPredicate judge){
if (!judge.test(o))
return o -Integer.signum(n -o);
for (int m = 0;1 < abs(n -o);)
m = judge.test(m = o +n >>1) ? (o = m) : (n = m);
return o;
}
protected long bSearchL(long o,long n,LongPredicate judge){
for (long m = 0;1 < abs(n -o);)
m = judge.test(m = o +n >>1) ? (o = m) : (n = m);
return o;
}
protected double bSearchD(double o,double n,DoublePredicate judge){
for (double m,c = 0;c < 100;c++)
m = judge.test(m = (o +n) /2) ? (o = m) : (n = m);
return o;
}
protected long gcd(long a,long b){
while (0 < b) {
long t = a;
a = b;
b = t %b;
}
return a;
}
public long lcm(long a,long b){ return b /gcd(a,b) *a; }
protected long ceil(long a,long b){ return (a +b -1) /b; }
}
class Util{
public static String yes = "Yes",no = "No";
public static int infI = (1 <<30) -1;
public static long infL = (1L <<61 |1 <<30) -1,
mod = 998244353;
public static Random rd = ThreadLocalRandom.current();
private long st = System.currentTimeMillis();
protected long elapsed(){ return System.currentTimeMillis() -st; }
protected void reset(){ st = System.currentTimeMillis(); }
public static int[] arrI(int N,IntUnaryOperator f){
int[] ret = new int[N];
setAll(ret,f);
return ret;
}
public static long[] arrL(int N,IntToLongFunction f){
long[] ret = new long[N];
setAll(ret,f);
return ret;
}
public static double[] arrD(int N,IntToDoubleFunction f){
double[] ret = new double[N];
setAll(ret,f);
return ret;
}
public static <T> T[] arr(T[] arr,IntFunction<T> f){
setAll(arr,f);
return arr;
}
@SuppressWarnings("unchecked")
public static <T> T cast(Object obj){ return (T) obj; }
}
class MyReader{
private byte[] buf = new byte[1 <<16];
private int ptr,tail;
private InputStream in;
public MyReader(InputStream in){ this.in = in; }
private byte read(){
if (ptr == tail)
try {
tail = in.read(buf);
ptr = 0;
} catch (IOException e) {}
return buf[ptr++];
}
private boolean isPrintable(byte c){ return 32 < c && c < 127; }
private byte nextPrintable(){
byte ret = read();
while (!isPrintable(ret))
ret = read();
return ret;
}
public int it(){ return toIntExact(lg()); }
public int[] it(int N){ return Util.arrI(N,i -> it()); }
public int[][] it(int H,int W){ return Util.arr(new int[H][],i -> it(W)); }
public int idx(){ return it() -1; }
public int[] idx(int N){ return Util.arrI(N,i -> idx()); }
public int[][] idx(int H,int W){ return Util.arr(new int[H][],i -> idx(W)); }
public long lg(){
byte i = nextPrintable();
boolean negative = i == 45;
long n = negative ? 0 : i -'0';
while (isPrintable(i = read()))
n = 10 *n +i -'0';
return negative ? -n : n;
}
public long[] lg(int N){ return Util.arrL(N,i -> lg()); }
public long[][] lg(int H,int W){ return Util.arr(new long[H][],i -> lg(W)); }
public double dbl(){ return Double.parseDouble(str()); }
public double[] dbl(int N){ return Util.arrD(N,i -> dbl()); }
public double[][] dbl(int H,int W){ return Util.arr(new double[H][],i -> dbl(W)); }
public char[] ch(){ return str().toCharArray(); }
public char[][] ch(int H){ return Util.arr(new char[H][],i -> ch()); }
public String line(){
StringBuilder sb = new StringBuilder();
for (byte c;(c = read()) != '\n';)
sb.append((char) c);
return sb.toString();
}
public String str(){
StringBuilder sb = new StringBuilder();
sb.append((char) nextPrintable());
for (byte c;isPrintable(c = read());)
sb.append((char) c);
return sb.toString();
}
public String[] str(int N){ return Util.arr(new String[N],i -> str()); }
public String[][] str(int H,int W){ return Util.arr(new String[H][],i -> str(W)); }
}
class MyWriter{
private OutputStream out;
private byte[] buf = new byte[1 <<16],ibuf = new byte[20];
private int tail;
private boolean autoflush;
public MyWriter(OutputStream out,boolean autoflush){
this.out = out;
this.autoflush = autoflush;
}
public void flush(){
try {
out.write(buf,0,tail);
tail = 0;
} catch (IOException e) {
e.printStackTrace();
}
}
private void ln(){
write((byte) '\n');
if (autoflush)
flush();
}
private void write(byte b){
buf[tail++] = b;
if (tail == buf.length)
flush();
}
private void write(long n){
if (n < 0) {
n = -n;
write((byte) '-');
}
int i = ibuf.length;
do {
ibuf[--i] = (byte) (n %10 +'0');
n /= 10;
} while (n > 0);
while (i < ibuf.length)
write(ibuf[i++]);
}
private void print(Object obj){
if (obj instanceof Boolean)
print((boolean) obj ? Util.yes : Util.no);
else if (obj instanceof Integer)
write((int) obj);
else if (obj instanceof Long)
write((long) obj);
else if (obj instanceof char[])
for (char b:(char[]) obj)
write((byte) b);
else if (obj.getClass().isArray()) {
int l = Array.getLength(obj);
for (int i = 0;i < l;i++) {
print(Array.get(obj,i));
if (i +1 < l)
write((byte) ' ');
}
} else
print(Objects.toString(obj).toCharArray());
}
public void println(Object obj){
if (obj == null)
obj = "null";
if (obj instanceof Iterable<?>)
for (Object e:(Iterable<?>) obj)
println(e);
else if (obj.getClass().isArray() && Array.getLength(obj) > 0 && Array.get(obj,0).getClass().isArray()) {
int l = Array.getLength(obj);
for (int i = 0;i < l;i++)
println(Array.get(obj,i));
} else {
print(obj);
ln();
}
}
public void printlns(Object... o){
print(o);
ln();
}
}