Submission #991261 - AtCoder Grand Contest 006

Contest Duration: 2016-10-29 21:00:00+0900 - 2016-10-29 23:10:00+0900 (local time) (130 minutes) Back to Home

Submission #991261

Source Code Expand

import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayDeque;
import java.util.Deque;

/**
 *  http://agc006.contest.atcoder.jp/tasks/agc006_f
 * 
 * @author Cummin
 */
public class Main {
    static int N ; // N<10^5
    static int M ; // M<10^5
    static Node[] index ; 
    static Deque<Integer> queue = new ArrayDeque<>() ; // チェックが必要な点(辺)のキュー
    
    static int black_cnt ;

    public static void main(String[] args) {
        int IN[] ;
        IN = fast_read(2) ;
        N = IN[0] ;
        M = IN[1] ;
        index = new Node[N] ;
        // 双方向リンクに変更
        out_link = new int[2][200000] ; // link[0][*]は、リンク先(outbound)のノード番号。link[1][*]は次のリンクへのポインタ。(-1は終端)
        in_link = new int[2][200000] ; // link[0][*]は、リンク元(inbound)のノード番号。link[1][*]は次のリンクへのポインタ。(-1は終端)
        black_cnt = 0 ;
        for (int i=0 ; i<M; i++) {
            int x, y ;
            IN = fast_read(2) ;
            x = IN[0] -1 ;
            y = IN[1] -1 ;
            create(x, y) ;
        }
//        dump_tree() ;
        solve() ;
        System.out.println(black_cnt);
//        dump_tree() ;
//        dump_mat() ;
    }
    
    static class Node {
        int visit ;
        int inTheQ ;
        int to_out_link_list ;
        int out_link_size ;
        int to_in_link_list ;
        int in_link_size ;
        Node() {
            this.to_out_link_list = -1 ;
            this.to_in_link_list = -1 ;
        }
    }
    
    static int[][] out_link  ;
    static int out_link_p ;
    static int[][] in_link  ;
    static int in_link_p ;
    
    static void create(int x, int y) {
        if (index[x]==null) {
            index[x] = new Node() ;
        }
        if (index[y]==null) {
            index[y]= new Node() ;
        }
        //add(x, y) ;
//        System.out.printf("add_link (%d -> %d)\n", x+1, y+1) ;
        add_out_link(index[x] , y) ;
        add_in_link(x,index[y]) ;
        black_cnt ++ ;
    }
    static void add_in_link(int lnk, Node m) {
        if (m.to_in_link_list==-1) {
            m.to_in_link_list = in_link_p ;
            in_link[0][in_link_p] = lnk ;
            in_link[1][in_link_p] = -1 ;
            in_link_p ++ ;
            m.in_link_size ++ ;
            return ;
        }
        int ptr ;
        ptr = m.to_in_link_list ;
        while (in_link[1][ptr]!=-1) {
            ptr = in_link[1][ptr] ;
        }
        in_link[1][ptr] = in_link_p ;
        in_link[0][in_link_p] = lnk ;
        in_link[1][in_link_p] = -1 ;
        in_link_p ++ ;
        m.in_link_size ++ ;
        return ;
    }
    static void add_out_link(Node n, int lnk) {
        if (n.to_out_link_list==-1) {
            n.to_out_link_list = out_link_p ;
            out_link[0][out_link_p] = lnk ;
            out_link[1][out_link_p] = -1 ;
            out_link_p ++ ;
            n.out_link_size ++ ;
            return ;
        }
        int ptr ;
        ptr = n.to_out_link_list ;
        while (out_link[1][ptr]!=-1) {
            ptr = out_link[1][ptr] ;
        }
        out_link[1][ptr] = out_link_p ;
        out_link[0][out_link_p] = lnk ;
        out_link[1][out_link_p] = -1 ;
        out_link_p ++ ;
        n.out_link_size ++ ;
        return ;
    }
    static int get_link(Node n, int i) {
        int ptr  ;
        ptr = n.to_out_link_list ;
        for (int j=0 ; j < i; j++) {
            ptr = out_link[1][ptr] ;
            if (ptr == -1) System.out.printf("ERROR: get_link \n") ;
        }
        return out_link[0][ptr] ;
    }
    static boolean has_link(Node n, int i) {
        int ptr ;
        ptr = n.to_out_link_list ;
        for (int j=0; j < n.out_link_size ;j++) {
            if (i==out_link[0][ptr]) return true ;
            ptr = out_link[1][ptr] ;
        }
        return false ;
    }
    static void solve() {
        for (int i = 0; i < N; i++) {
            if (index[i] == null) {
                continue;
            } else {
                queue.add(i);
                index[i].inTheQ = 1;
            }
        }
        Integer p;
        while ((p = queue.poll()) != null) {
            //System.out.printf("Check node %d \n", p+1) ;
            index[p].inTheQ = 0;
            solve2(p);
        }
        //System.out.printf("black_cnt= %d s2_cnt=%d \n", black_cnt, s2_cnt) ;
    }
    static int s2_cnt  ; // for algorithm check
    static void solve2(int yy) { // Y中心のアルゴリズムに変更する
        s2_cnt ++ ;
        // yx_links (親(x)からのリンクがある時、自分(y)から子(z)のリンクを探して、(z,x)を追加する
        int yx_link_ptr = -1 ;
        if (index[yy].in_link_size>0) yx_link_ptr = index[yy].to_in_link_list;
        while (yx_link_ptr != -1) {
            int xx = in_link[0][yx_link_ptr] ;
            int yz_link_ptr = -1 ;
            if (index[yy].out_link_size>0) yz_link_ptr = index[yy].to_out_link_list ;
            while (yz_link_ptr != -1){
                int zz = out_link[0][yz_link_ptr] ;
                    //check_and_set(z, x);      
                    if (has_link(index[zz], xx)) {
                        //continue;
                    } else {
                        //add(x,y) ;
                        //System.out.printf("add_link (%d -> %d)\n", zz+1, xx+1) ;
                        add_out_link(index[zz], xx);
                        add_in_link(zz, index[xx]);
                        black_cnt++;
                        
                        if (index[xx].inTheQ==0) {
                            index[xx].inTheQ = 1 ;
                            queue.add(xx) ;
                        }
                    }
                    yz_link_ptr = out_link[1][yz_link_ptr] ;
            }
            yx_link_ptr = in_link[1][yx_link_ptr] ;
        }
    }

    static void dump_mat() {
        for (int iy=0 ;iy<N ;iy++) {
            for (int ix=0 ;ix<N; ix++) {
                if (index[ix]== null) {
                    System.out.printf(".") ;
                } else if (has_link(index[ix], iy)) {
                    System.out.printf("*") ;
                } else System.out.printf(".") ;
            }
            System.out.println() ;
        }
    }
    static void dump_tree() {
        System.out.println();
        for (int i = 0; i < N; i++) {
            if (index[i] == null) {
                continue;
            }
            System.out.printf("OUTBOUND:[%d]:", i+1);
            int ptr = index[i].to_out_link_list ;
            for (int j=0 ; j< index[i].out_link_size ; j++) {
                int k = out_link[0][ptr] ;
                System.out.printf("--> %d ", k+1);
                ptr = out_link[1][ptr] ;
            }
            System.out.println();
            System.out.printf("INBOUND :[%d]:", i+1);
            ptr = index[i].to_in_link_list ;
            for (int j=0 ; j< index[i].in_link_size ; j++) {
                int k = in_link[0][ptr] ;
                System.out.printf("--> %d ", k+1);
                ptr = in_link[1][ptr] ;
            }
            System.out.println();
        }
        System.out.println();
    }
    //////////////// 高速読み込み //////////////////////
    
    static int[] fast_read(int N) {
        int elements[] = new int[N];
        int e_cnt = 0;
        char c;
        while (e_cnt < N) {
            c = get_char() ;
            if ((c < '0') || ('9' < c)) {
                continue; // Skip 非数値文字
            }
            elements[e_cnt] = 0;
            while (('0' <= c) && (c <= '9')) {  // 数値文字を変換する
                elements[e_cnt] = elements[e_cnt] * 10 + (int) c - '0';
                c = get_char() ;
            }
//            System.out.printf("\nelement[%d] = %d \n", e_cnt + 1, elements[e_cnt]);
            e_cnt++;
        }
        return elements;
    }
    
    ///////////////// get_char() /////////////////////////////////
    //static char c_buf[] = new char[1024*1024];
    static byte[] __c_buf = new byte[1024*1024];
    static int __ptr = 0 ;
    static int __c_len = 0 ;
    //static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static InputStream __ins = System.in;

    static char get_char() {
        char ret;

        if (__ptr >= __c_len) {
            try {
                //c_len = br.read(c_buf);
                __c_len = __ins.read(__c_buf);
            } catch (IOException ex) {
               ex.printStackTrace();
               System.exit(-1); // 終了する
            }
            __ptr = 0;
        }
        ret = (char) __c_buf[__ptr];
        __ptr++;
        return ret;
    }
}

Submission Info

Submission Time	2016-11-26 11:04:45+0900
Task	F - Blackout
User	Cummin
Language	Java8 (OpenJDK 1.8.0)
Score	0
Code Size	9020 Byte
Status	TLE
Exec Time	2104 ms
Memory	36396 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

0 / 1700

Status

× 3

AC	× 7
TLE	× 6
RE	× 40

Set Name	Test Cases
Sample	0_00.txt, 0_01.txt, 0_02.txt
All	0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt

Case Name	Status	Exec Time	Memory
0_00.txt	AC	99 ms	12236 KiB
0_01.txt	AC	97 ms	12236 KiB
0_02.txt	AC	99 ms	12108 KiB
1_00.txt	AC	99 ms	12236 KiB
1_01.txt	AC	102 ms	12620 KiB
1_02.txt	AC	167 ms	22348 KiB
1_03.txt	RE	202 ms	36396 KiB
1_04.txt	TLE	2104 ms	24324 KiB
1_05.txt	TLE	2104 ms	24468 KiB
1_06.txt	RE	206 ms	36388 KiB
1_07.txt	RE	199 ms	36284 KiB
1_08.txt	RE	205 ms	36192 KiB
1_09.txt	RE	202 ms	36124 KiB
1_10.txt	RE	198 ms	36100 KiB
1_11.txt	RE	203 ms	36272 KiB
1_12.txt	RE	198 ms	36116 KiB
1_13.txt	AC	171 ms	22728 KiB
1_14.txt	TLE	2104 ms	16332 KiB
1_15.txt	TLE	2104 ms	16332 KiB
1_16.txt	TLE	2104 ms	18132 KiB
1_17.txt	TLE	2104 ms	15364 KiB
1_18.txt	RE	202 ms	23320 KiB
1_19.txt	RE	199 ms	23340 KiB
1_20.txt	RE	200 ms	23184 KiB
1_21.txt	RE	199 ms	23356 KiB
1_22.txt	RE	199 ms	23324 KiB
1_23.txt	RE	200 ms	23532 KiB
1_24.txt	RE	200 ms	23264 KiB
1_25.txt	RE	206 ms	23404 KiB
1_26.txt	RE	198 ms	23272 KiB
1_27.txt	RE	198 ms	23308 KiB
1_28.txt	RE	202 ms	23304 KiB
1_29.txt	RE	202 ms	23532 KiB
1_30.txt	RE	199 ms	23196 KiB
1_31.txt	RE	200 ms	23160 KiB
1_32.txt	RE	201 ms	23240 KiB
1_33.txt	RE	198 ms	23324 KiB
1_34.txt	RE	197 ms	22236 KiB
1_35.txt	RE	192 ms	20188 KiB
1_36.txt	RE	195 ms	20972 KiB
1_37.txt	RE	198 ms	22808 KiB
1_38.txt	RE	185 ms	19448 KiB
1_39.txt	RE	192 ms	19136 KiB
1_40.txt	RE	198 ms	23040 KiB
1_41.txt	RE	198 ms	22924 KiB
1_42.txt	RE	189 ms	20432 KiB
1_43.txt	RE	198 ms	20396 KiB
1_44.txt	RE	197 ms	22316 KiB
1_45.txt	RE	194 ms	18860 KiB
1_46.txt	RE	198 ms	22652 KiB
1_47.txt	RE	199 ms	23148 KiB
1_48.txt	RE	187 ms	19908 KiB
1_49.txt	RE	200 ms	21412 KiB