阿祁的部落格

AtCoder Regular Contest 142 C - Tree Queries 解題心得( 題目 )

解題概念:樹

解題方法:首先利用2n-4個查詢得到1、2和其他點的距離，接著利用這些資訊討論答案。

//Author:En Chi Tsung(欉恩祁)
//Date:2022/06/22
import java.util.*;
import java.time.*;
import java.io.*;
import java.math.*;
public class Main {
    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
    public static long ret;
    public static int reti,rd;
    public static boolean neg;
    public static final int mod=998244353;
    public static final int mod2=1_000_000_007;
    public static Useful us=new Useful(mod2);
    public static void main(String[] args) throws Exception{
        final int n=readint();
        int[][] dist=new int[n+5][3];
        us.arr(dist,1<<28);
        for(int i=1;i<=2;i++) {
            for(int j=3;j<=n;j++) {
                System.out.println("? "+i+" "+j);
                System.out.flush();
                dist[j][i]=readint();
            }
        }
        int ans=(1<<30);
        ArrayList<Integer> c1=new ArrayList<>();
        ArrayList<Integer> c2=new ArrayList<>();
        int de=0;
        for(int i=3;i<=n;i++) {
            ans=Math.min(dist[i][1]+dist[i][2],ans);
            if(dist[i][1]>dist[i][2]) {
                c2.add(i);
            }
            if(dist[i][1]<dist[i][2]) {
                c1.add(i);
            }
        }
        if((c1.isEmpty()||c2.isEmpty())&&n!=3) {
            int mux=1;
            for(int i=3;i<=n;i++) {
                mux=Math.max(mux,dist[i][1]-dist[i][2]);
            }
            ans=Math.min(mux,ans);
        }
        else if(c1.size()+c2.size()==n-2) {
            int l=c1.get(0);
            int r=c2.get(0);
            int y;
            System.out.println("? "+l+" "+r);
            System.out.flush();
            y=readint();
            if(y<dist[l][1]+dist[r][2]) {
                ans=Math.min(Math.abs(y+dist[l][1]+dist[r][2]),ans);
            }
            else {
                ans=Math.min(Math.max(y-dist[l][1]-dist[r][2],dist[l][2]+dist[r][1]-y),ans);
            }
        }
        System.out.println("! "+ans);
        
    }
    public static int readint() throws Exception{
        reti=0;
        neg=false;
        while(rd<48||rd>57) {
            rd=br.read();
            if(rd=='-') {
                neg=true;
            }
        }
        while(rd>47&&rd<58) {
            reti*=10;
            reti+=(rd&15);
            rd=br.read();
        }
        if(neg)reti*=-1;
        return reti;
    }
    
    public static long readlong() throws Exception{
        ret=0;
        neg=false;
        while(rd<48||rd>57) {
            rd=br.read();
            if(rd=='-') {
                neg=true;
            }
        }
        while(rd>47&&rd<58) {
            ret*=10;
            ret+=(rd&15);
            rd=br.read();
        }
        if(neg)ret*=-1;
        return ret;
    }
}
/*

 */

/*

 */

class Pii{
    int x;
    long y;
    Pii(int a,long b){
        x=a;
        y=b;
    }
}

class Pll{
    long x,y;
    Pll(long a,long b){
        x=a;
        y=b;
    }
}

class Useful{
    long mod;
    Useful(long m){mod=m;}
    void al(ArrayList<ArrayList<Integer>> a,int n){for(int i=0;i<n;i++) {a.add(new ArrayList<Integer>());}}
    void arr(int[] a,int init) {for(int i=0;i<a.length;i++) {a[i]=init;}}
    void arr(long[] a,long init) {for(int i=0;i<a.length;i++) {a[i]=init;}}
    void arr(int[][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {a[i][j]=init;}}}
    void arr(long[][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {a[i][j]=init;}}}
    void arr(int[][][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {a[i][j][k]=init;}}}}
    void arr(long[][][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {a[i][j][k]=init;}}}}
    void arr(int[][][][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {Arrays.fill(a[i][j][k],init);}}}}
    void arr(long[][][][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {Arrays.fill(a[i][j][k],init);}}}}
    long fast(long x,long pw) {
        if(pw<=0)return 1;
        if(pw==1)return x;
        long h=fast(x,pw>>1);
        if((pw&1)==0) {
            return h*h%mod;
        }
        return h*h%mod*x%mod;
    }
    long[][] mul(long[][] a,long[][] b){
        long[][] c=new long[a.length][b[0].length];
        for(int i=0;i<a.length;i++) {
            for(int j=0;j<b[0].length;j++) {
                for(int k=0;k<a[0].length;k++) {
                    c[i][j]+=a[i][k]*b[k][j];
                    c[i][j]%=mod;
                }
            }
        }
        return c;
    }

    long[][] fast(long[][] x,int pw){
        if(pw==1)return x;
        long[][] h=fast(x,pw>>1);
        if((pw&1)==0) {
            return mul(h,h);
        }
        else {
            return mul(mul(h,h),x);
        }
    }
    int gcd(int a,int b) {
        if(a==0)return b;
        if(b==0)return a;
        return gcd(b,a%b);
    }
    long gcd(long a,long b) {
        if(a==0)return b;
        if(b==0)return a;
        return gcd(b,a%b);
    }
    long lcm(long a, long b){
        return a*(b/gcd(a,b));
    }
    double log2(int x) {
        return (Math.log(x)/Math.log(2));
    }
    double log2(long x) {
        return (Math.log(x)/Math.log(2));
    }
}