Submission #3169078
Source Code Expand
#include <stdio.h>
#include <stdlib.h>
#define inf (int)(1e9 + 7)
#define dag_valtype int
#define graph_valtype int
typedef struct graph_edge_sub graph_edge;
typedef struct {
int num;
int next_num;
graph_edge *next;
int prev_num;
}graph_vertex_sub;
struct graph_edge_sub{
graph_vertex_sub *v;
int w;
graph_edge *next;
};
typedef struct graph_v_sub graph_vertex;
struct graph_v_sub{
int num;
graph_valtype val;
int next_num;
graph_vertex **next;
int *next_weight;
int prev_num;
graph_vertex **prev;
int *prev_weight;
};
typedef struct {
int N;
graph_vertex_sub **v_s;
graph_vertex **v;
}graph;
//頂点数N, 各頂点の初期値ini_valのグラフを作る
graph *make_graph(int N, graph_valtype ini_val){
int i;
graph *g = (graph *)malloc(sizeof(graph));
g->N = N;
g->v_s = (graph_vertex_sub **)malloc(sizeof(graph_vertex_sub *) * N);
g->v = (graph_vertex **)malloc(sizeof(graph_vertex *) * N);
for(i = 0; i < N; i++){
(g->v_s)[i] = (graph_vertex_sub *)malloc(sizeof(graph_vertex_sub));
(g->v_s)[i]->num = i;
(g->v_s)[i]->next_num = 0;
(g->v_s)[i]->next = NULL;
(g->v_s)[i]->prev_num = 0;
(g->v)[i] = (graph_vertex *)malloc(sizeof(graph_vertex));
(g->v)[i]->num = i;
(g->v)[i]->val = ini_val;
(g->v)[i]->next_num = 0;
(g->v)[i]->next = NULL;
(g->v)[i]->next_weight = NULL;
(g->v)[i]->prev_num = 0;
(g->v)[i]->prev = NULL;
(g->v)[i]->prev_weight = NULL;
}
return g;
}
//グラフgの頂点aから頂点bに重みwの有向辺を張る (0 <= a, b <= N - 1)
void set_edge_graph(int a, int b, int w, graph *g){
graph_edge *new1 = (graph_edge *)malloc(sizeof(graph_edge));
new1->v = (g->v_s)[b];
new1->w = w;
new1->next = (g->v_s)[a]->next;
(g->v_s)[a]->next = new1;
(g->v_s)[a]->next_num++;
(g->v_s)[b]->prev_num++;
}
//set_edge_graph後に呼び出す
void build_graph(graph *g){
int i;
graph_vertex_sub **v_s = g->v_s;
graph_vertex **v = g->v;
graph_vertex *nowv;
graph_edge *nowe;
for(i = 0; i < g->N; i++){
v[i]->next = (graph_vertex **)malloc(sizeof(graph_vertex *) * v_s[i]->next_num);
v[i]->next_weight = (int *)malloc(sizeof(int) * v_s[i]->next_num);
v[i]->prev = (graph_vertex **)malloc(sizeof(graph_vertex *) * v_s[i]->prev_num);
v[i]->prev_weight = (int *)malloc(sizeof(int) * v_s[i]->prev_num);
}
for(i = 0; i < g->N; i++){
nowv = v[i];
for(nowe = v_s[i]->next; nowe != NULL; nowe = nowe->next){
(nowv->next)[nowv->next_num] = v[nowe->v->num];
(nowv->next_weight)[nowv->next_num] = nowe->w;
nowv->next_num++;
(v[nowe->v->num]->prev)[v[nowe->v->num]->prev_num] = nowv;
(v[nowe->v->num]->prev_weight)[v[nowe->v->num]->prev_num] = nowe->w;
v[nowe->v->num]->prev_num++;
}
}
}
typedef struct SCC_sub{
int num; //強連結成分番号
int vertex_num; //強連結成分に含まれる頂点の個数
int *vertexs; //強連結成分に含まれる元のグラフでの頂点番号
dag_valtype val;
int next_num;
struct SCC_sub **next;
int *next_weight;
int prev_num;
struct SCC_sub **prev;
int *prev_weight;
}SCC; //強連結成分(Strongly Connected Components)
typedef struct {
int N;
SCC **sorted_SCC; //topological sort済み
}DAG; //非閉路有向グラフ(Directed Acyclic Graph)
int dfs(int next_bt, int *used, int *bt, int *bt_inv, graph_vertex *v){
if(used[v->num] == 1){
return next_bt;
}
else{
int i;
used[v->num] = 1;
for(i = 0; i < v->next_num; i++){
next_bt = dfs(next_bt, used, bt, bt_inv, v->next[i]);
}
bt[v->num] = next_bt;
bt_inv[next_bt] = v->num;
return next_bt + 1;
}
}
void dfs_rev1(int next_SCC_num, int *used, int *SCC_num, int *next_num, int *prev_num, graph_vertex *v){
if(used[v->num] == 1){
int i;
used[v->num] = 2;
for(i = 0; i < v->prev_num; i++){
dfs_rev1(next_SCC_num, used, SCC_num, next_num, prev_num, v->prev[i]);
}
SCC_num[v->num] = next_SCC_num;
for(i = 0; i < v->next_num; i++){
if(used[v->next[i]->num] == 1){
next_num[v->num]++;
prev_num[v->next[i]->num]++; //ここで自己ループを数えてしまう可能性がある
}
}
}
}
void dfs_rev2(SCC *now_SCC, int *used, int *SCC_num, graph_vertex *v, DAG *dag){
if(used[v->num] == 2){
int i;
SCC *next_SCC;
used[v->num] = 3;
for(i = 0; i < v->prev_num; i++){
dfs_rev2(now_SCC, used, SCC_num, v->prev[i], dag);
}
now_SCC->vertexs[now_SCC->vertex_num] = v->num;
now_SCC->vertex_num++;
for(i = 0; i < v->next_num; i++){
if(used[v->next[i]->num] == 2){
next_SCC = dag->sorted_SCC[SCC_num[v->next[i]->num]];
if(now_SCC->num != next_SCC->num){ //自己ループがないようにしている
now_SCC->next[now_SCC->next_num] = next_SCC;
now_SCC->next_weight[now_SCC->next_num] = v->next_weight[i];
now_SCC->next_num++;
next_SCC->prev[next_SCC->prev_num] = now_SCC;
next_SCC->prev_weight[next_SCC->prev_num] = v->next_weight[i];
next_SCC->prev_num++;
}
}
}
}
}
DAG *build_DAG(graph *g, dag_valtype ini_val){
int N = g->N, i;
int *used = (int *)malloc(sizeof(int) * N);
int *bt = (int *)malloc(sizeof(int) * N);
int *bt_inv = (int *)malloc(sizeof(int) * N);
for(i = 0; i < N; i++){
used[i] = 0;
bt[i] = -1;
bt_inv[i] = -1;
}
int next_bt;
for(i = 0, next_bt = 0; i < N; i++){
next_bt = dfs(next_bt, used, bt, bt_inv, g->v[i]);
}
int *SCC_num = (int *)malloc(sizeof(int) * N);
int *next_num = (int *)malloc(sizeof(int) * N);
int *prev_num = (int *)malloc(sizeof(int) * N);
for(i = 0; i < N; i++){
SCC_num[i] = 0;
next_num[i] = 0;
prev_num[i] = 0;
}
int next_SCC_num;
for(i = N - 1, next_SCC_num = 0; i >= 0; i--){
if(used[bt_inv[i]] == 1){
dfs_rev1(next_SCC_num, used, SCC_num, next_num, prev_num, g->v[bt_inv[i]]);
next_SCC_num++;
}
}
DAG *dag = (DAG *)malloc(sizeof(DAG));
SCC *now_SCC;
dag->N = next_SCC_num;
dag->sorted_SCC = (SCC **)malloc(sizeof(SCC *) * dag->N);
for(i = 0; i < dag->N; i++){
dag->sorted_SCC[i] = (SCC *)malloc(sizeof(SCC));
now_SCC = dag->sorted_SCC[i];
now_SCC->num = i;
now_SCC->vertex_num = 0;
now_SCC->vertexs = NULL;
now_SCC->val = ini_val;
now_SCC->next_num = 0;
now_SCC->next = NULL;
now_SCC->next_weight = NULL;
now_SCC->prev_num = 0;
now_SCC->prev = NULL;
now_SCC->prev_weight = NULL;
}
for(i = 0; i < N; i++){
now_SCC = dag->sorted_SCC[SCC_num[i]];
now_SCC->vertex_num++;
now_SCC->next_num += next_num[i];
now_SCC->prev_num += prev_num[i];
}
for(i = 0; i < dag->N; i++){
now_SCC = dag->sorted_SCC[i];
now_SCC->vertexs = (int *)malloc(sizeof(int) * now_SCC->vertex_num);
now_SCC->next = (SCC **)malloc(sizeof(SCC *) * now_SCC->next_num);
now_SCC->next_weight = (int *)malloc(sizeof(int) * now_SCC->next_num);
now_SCC->prev = (SCC **)malloc(sizeof(SCC *) * now_SCC->prev_num);
now_SCC->prev_weight = (int *)malloc(sizeof(int) * now_SCC->prev_num);
now_SCC->vertex_num = 0;
now_SCC->next_num = 0;
now_SCC->prev_num = 0;
}
for(i = N - 1, next_SCC_num = 0; i >= 0; i--){
if(used[bt_inv[i]] == 2){
dfs_rev2(dag->sorted_SCC[next_SCC_num], used, SCC_num, g->v[bt_inv[i]], dag);
next_SCC_num++;
}
}
return dag;
}
typedef struct {
int *array;
int last;
int first;
}queue;
queue *make_queue(int maxN){
queue *q = (queue *)malloc(sizeof(queue));
q->array = (int *)malloc(sizeof(int) * maxN);
q->last = 0;
q->first = 0;
return q;
}
int element_num_queue(queue *q){
return q->first - q->last;
}
void add_data_queue(int val, queue *q){
q->array[q->first] = val;
q->first++;
}
int take_data_queue(queue *q){
if(element_num_queue(q) <= 0){
printf("no data in the queue\n");
}
q->last++;
return q->array[q->last - 1];
}
void flush_queue(queue *q){
q->last = 0;
q->first = 0;
}
int min(int a, int b){
return a <= b ? a : b;
}
//n:頂点数, s:始点の番号, t:終点の番号, e:(u, v)->f uからvへの容量
int Edmonds_Karp(int N, int s, int t, int **e){
int v, i, flow_sum = 0;
int *flow = (int *)malloc(sizeof(int) * N);//各頂点に流せるフロー
int *p = (int *)malloc(sizeof(int) * N);//増加道の履歴 前の頂点を入れる
queue *q = make_queue(N * N);
int j;
int **nexts = (int **)malloc(sizeof(int *) * N);
int *nexts_num = (int *)malloc(sizeof(int) * N);
for(i = 0; i < N; i++){
nexts[i] = (int *)malloc(sizeof(int) * N);
nexts_num[i] = 0;
for(j = 0; j < N; j++){
if(e[i][j] != 0 || e[j][i] != 0){
nexts[i][nexts_num[i]] = j;
nexts_num[i]++;
}
}
}
for(;;){
//初期化
for(i = 0; i < N; i++){
flow[i] = 0;
p[i] = -1;
}
flow[s] = inf;
p[s] = -2;
add_data_queue(s, q);
while(element_num_queue(q) > 0){
v = take_data_queue(q);
if(v == t){
break;
}
for(i = 0; i < nexts_num[v]; i++){
j = nexts[v][i];
if(e[v][j] > 0 && p[j] == -1){
p[j] = v;
flow[j] = min(flow[v], e[v][j]);
add_data_queue(j, q);
}
}
}
//増加道がなかった場合
if(flow[t] == 0){
break;
}
//残余ネットワークの構築
for(v = t; v != s; v = p[v]){
e[p[v]][v] -= flow[t];
e[v][p[v]] += flow[t];
}
flow_sum += flow[t];
flush_queue(q);
}
return flow_sum;
}
int main(){
int N, L, i, j;
scanf("%d", &N);
L = 4000;
int **e = (int **)malloc(sizeof(int *) * 2 * (L + 1));
for(i = 0; i < 2 * (L + 1); i++){
e[i] = (int *)malloc(sizeof(int) * 2 * (L + 1));
for(j = 0; j < 2 * (L + 1); j++){
e[i][j] = 0;
}
}
int *R = (int *)malloc(sizeof(int) * N);
int *C = (int *)malloc(sizeof(int) * N);
for(i = 0; i < N; i++){
scanf("%d%d", &R[i], &C[i]);
e[R[i]][L + C[i]] = 1;
}
for(i = 1; i <= L; i++){
e[0][i] = 1;
e[L + i][2 * L + 1] = 1;
}
int maxflow = Edmonds_Karp(2 * (L + 1), 0, 2 * L + 1, e);
printf("%d\n", N - maxflow);
graph *g = make_graph(2 * (L + 1), 0);
for(i = 0; i < 2 * (L + 1); i++){
for(j = 0; j < 2 * (L + 1); j++){
if(e[i][j] > 0){
set_edge_graph(i, j, e[i][j], g);
}
}
}
build_graph(g);
DAG *dag = build_DAG(g, 0);
int *SCC_num = (int *)malloc(sizeof(int) * 2 * (L + 1));
SCC *now_SCC;
for(i = 0; i < dag->N; i++){
now_SCC = dag->sorted_SCC[i];
for(j = 0; j < now_SCC->vertex_num; j++){
SCC_num[now_SCC->vertexs[j]] = i;
}
}
for(i = 0; i < N; i++){
if(SCC_num[R[i]] == SCC_num[C[i] + L]){
printf("0\n");
}
else{
if(e[R[i]][C[i] + L] == 1){
printf("1\n");
}
else{
printf("-1\n");
}
}
}
return 0;
}
Submission Info
Submission Time
2018-09-09 20:11:20+0900
Task
I - ルーク
User
abc050
Language
C (GCC 5.4.1)
Score
0
Code Size
10743 Byte
Status
TLE
Exec Time
2122 ms
Memory
290048 KB
Compile Error
./Main.c: In function ‘main’:
./Main.c:360:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
^
./Main.c:372:3: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &R[i], &C[i]);
^
Judge Result
Set Name
sample
all
Score / Max Score
0 / 0
0 / 1
Status
Set Name
Test Cases
sample
sample-01.txt, sample-02.txt
all
sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt, 01-41.txt, 01-42.txt, sample-01.txt, sample-02.txt
Case Name
Status
Exec Time
Memory
01-01.txt
MLE
1373 ms
287232 KB
01-02.txt
MLE
1373 ms
287232 KB
01-03.txt
MLE
1485 ms
287104 KB
01-04.txt
MLE
1560 ms
287104 KB
01-05.txt
MLE
1609 ms
287104 KB
01-06.txt
TLE
2121 ms
282752 KB
01-07.txt
TLE
2121 ms
282880 KB
01-08.txt
TLE
2120 ms
282880 KB
01-09.txt
MLE
1670 ms
287488 KB
01-10.txt
TLE
2120 ms
284416 KB
01-11.txt
TLE
2121 ms
282880 KB
01-12.txt
MLE
1413 ms
290048 KB
01-13.txt
MLE
1540 ms
289920 KB
01-14.txt
MLE
1783 ms
289792 KB
01-15.txt
MLE
1782 ms
289664 KB
01-16.txt
MLE
1784 ms
289664 KB
01-17.txt
TLE
2121 ms
283392 KB
01-18.txt
TLE
2122 ms
283392 KB
01-19.txt
TLE
2121 ms
283392 KB
01-20.txt
TLE
2121 ms
283392 KB
01-21.txt
TLE
2121 ms
283392 KB
01-22.txt
TLE
2121 ms
283392 KB
01-23.txt
TLE
2121 ms
283392 KB
01-24.txt
TLE
2120 ms
283392 KB
01-25.txt
TLE
2121 ms
283392 KB
01-26.txt
TLE
2121 ms
283392 KB
01-27.txt
TLE
2121 ms
283392 KB
01-28.txt
TLE
2120 ms
285312 KB
01-29.txt
TLE
2122 ms
283264 KB
01-30.txt
MLE
1509 ms
287104 KB
01-31.txt
MLE
1688 ms
286592 KB
01-32.txt
TLE
2067 ms
288896 KB
01-33.txt
MLE
1512 ms
287104 KB
01-34.txt
MLE
1708 ms
286592 KB
01-35.txt
MLE
1927 ms
288768 KB
01-36.txt
MLE
1468 ms
288896 KB
01-37.txt
TLE
2121 ms
283392 KB
01-38.txt
MLE
1364 ms
286464 KB
01-39.txt
MLE
1360 ms
286464 KB
01-40.txt
MLE
1367 ms
286720 KB
01-41.txt
MLE
1364 ms
287104 KB
01-42.txt
MLE
1589 ms
287232 KB
sample-01.txt
MLE
1355 ms
287232 KB
sample-02.txt
MLE
1365 ms
287232 KB