Cod sursa(job #2016995)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 31 august 2017 00:41:00
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 2.1 kb
#pragma GCC optimize ("O3")
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef struct vector{
    int sz, capacity, *buf; } vector;

int i, n, m, *tmp, cur, *p, x, y, j, int_rez;
FILE *f, *g;
char i_buf[100000] = {}, *i_buf_p = i_buf, *i_buf_ep = i_buf + sizeof(i_buf), o_buf[300000] = {}, *o_buf_p = o_buf,
    tmp_o_buf[10], *tmp_o_buf_p = tmp_o_buf;
vector vec[50010];
int nr_prevs[50010] = {}, st[50010], *st_p = st, rez[50010], *rez_p = rez;
 
static int get_int(){
    int_rez = 0, j = 0;
    LOOP0:
    if(*i_buf_p >= '0') j = 1, int_rez = 10 * int_rez + *i_buf_p - '0';
    else if(j == 1) return int_rez;
    if(++i_buf_p == i_buf_ep) fread(i_buf_p = i_buf, sizeof(char), sizeof(i_buf), f);
    goto LOOP0; }

int main(){
    f = fopen("sortaret.in", "r"),
    fread(i_buf_p = i_buf, sizeof(char), sizeof(i_buf), f);
    g = fopen("sortaret.out", "w");
 
    n = get_int(), m = get_int();

    i = 0;
    LOOP3: if(i < n) {
    vec[i].sz = 0;
    vec[i].capacity = 4;
    vec[i].buf = malloc(4 * sizeof(int));
    ++i;
    goto LOOP3; }

    i = 0;
    LOOP4: if(i < m) {
    x = get_int(), y = get_int();

    --x, --y;
    if(vec[x].sz == vec[x].capacity) {
        tmp = malloc(2 * vec[x].capacity * sizeof(int));
        memcpy(tmp, vec[x].buf, vec[x].capacity * sizeof(int));
        vec[x].buf = tmp;
        vec[x].capacity *= 3;
        vec[x].capacity /= 2; }
    vec[x].buf[vec[x].sz++] = y; 
    ++nr_prevs[y];
    ++i;
    goto LOOP4; }

    i = 0;
    LOOP5: if(i < n) {
    if(nr_prevs[i] == 0) *st_p++ = i;
    ++i;
    goto LOOP5; }


    LOOP6: if(st_p != st) {
    cur = *--st_p;
    *rez_p++ = cur;
    i = 0;
    LOOP7: if(i < vec[cur].sz){
    if(--nr_prevs[vec[cur].buf[i]] == 0) *st_p++ = vec[cur].buf[i];
    ++i;
    goto LOOP7; }
    goto LOOP6; }


    p = rez;
    LOOP8: if(p < rez_p) {
    ++*p;

    LOOP1: if(*p) {
    *tmp_o_buf_p++ = *p % 10 + '0';
    *p /= 10;
    goto LOOP1; }

    LOOP2: if(tmp_o_buf_p > tmp_o_buf) {
    *o_buf_p++ = *--tmp_o_buf_p;
    goto LOOP2; }
    *o_buf_p++ = ' '; 
    ++p;
    goto LOOP8; }
 
    fwrite(o_buf, o_buf_p - o_buf, sizeof(char), g);
    return 0; }