oj.uz

Submission #300429

# Submission time Handle Problem Language Result Execution time Memory
300429 2020-09-17T07:10:49 Z bacegen4o Graph (BOI20_graph) C
100 / 100
 189 ms 12792 KB 
#pragma GCC optimize "-O3"
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<assert.h>
#include<stdbool.h>
#include<limits.h>
int cmp(const void * a, const void * b){ return ( *(int*)a - *(int*)b ); }
typedef struct{
  int first, second;
}pair;
pair newpair(int a, int b){
  return(pair){a,b};
}
#define pbp(zpv, zvv) zpv.ptr = pushbackP(zpv.ptr, &zpv.sz, zvv)
#define resizeArray(ptr, type, size) ((type*)realloc(ptr, (size) * sizeof(type)))
pair*pushbackP(pair*array, int*size, pair value){
  pair*output = resizeArray(array, pair, *size + 1);
  output[(*size)++] = value;
  return output;
}
typedef struct{
	pair*ptr;
	int sz;
}vecp;
vecp newVecP(){
	vecp rez;
	rez.ptr = NULL;
	rez.sz  = 0;
	return rez;
}
#if 1 //queueue
typedef int QueueElementType;
typedef struct Queue
{
  QueueElementType  *Elements;
  int  Front;
  int  Back;
  int  NumElements;
  int  Capacity;
} Queue;
Queue *newQueue();
void   DeleteQueue(Queue *Q);
int    empty(Queue *Q);
int    push(Queue *Q, QueueElementType e);
QueueElementType pop(Queue *Q);
int    isElementInQueue(Queue *Q, QueueElementType e);

Queue *newQueue()
{
  int N=1024;
  Queue *Q;
  if (N < 1)
  {
    printf("\n**Error in newQueue invalid parameter N (%d)\n\n", N);
    return NULL;
  }
  Q = (Queue *)malloc(sizeof(Queue));
  if (Q == NULL)
  {
    printf("\n**Error in newQueue: malloc failed _to allocate\n\n");
    exit(-1);
  }
  Q->Elements = (QueueElementType *)malloc(N * sizeof(QueueElementType));
  if (Q->Elements == NULL)
  {
    printf("\n**Error in newQueue: malloc failed _to allocate\n\n");
    exit(-1);
  }
  Q->Front = 0;
  Q->Back = -1;
  Q->NumElements = 0;
  Q->Capacity = N;
  return Q;
}
void DeleteQueue(Queue *Q)
{
  free(Q->Elements);
  free(Q);
}
int empty(Queue *Q)
{
  return Q->NumElements == 0;
}
int size(Queue *Q)
{
  return Q->NumElements;
}
int push(Queue *Q, QueueElementType e)
{
  if (Q->NumElements == Q->Capacity)
  {
    int N = 2 * Q->Capacity;
    QueueElementType *newE = (QueueElementType *)malloc(N * sizeof(QueueElementType));
    if (newE == NULL)
    {
      printf("\n**Error in push: malloc failed _to allocate\n\n");
      exit(-1);
    }
    int  i = Q->Front;
    int  j = 0;
    int  n;
    for (n = 0; n < Q->NumElements; ++n)
    {
      newE[j] = Q->Elements[i];
      ++j;
      ++i;
      if (i >= Q->Capacity)
        i = 0;
    }
    free(Q->Elements);
    Q->Front = 0;
    Q->Back = j - 1;
    Q->Elements = newE;
    Q->Capacity = N;
  }
  Q->Back++;
  if (Q->Back >= Q->Capacity)
    Q->Back = 0;
  Q->Elements[Q->Back] = e;
  Q->NumElements++;
  return 1;
}
QueueElementType pop(Queue *Q)
{
  if (empty(Q))
  {
    printf("\n**Error in pop: Q is empty?!\n\n");
    exit(-1);
  }
  QueueElementType e = Q->Elements[Q->Front];
  Q->Front++;
  if (Q->Front >= Q->Capacity)
    Q->Front = 0;
  Q->NumElements--;
  return e;
}
QueueElementType front(Queue *Q)
{
  if (empty(Q))
  {
    printf("\n**Error in pop: Q is empty?!\n\n");
    exit(-1);
  }
  QueueElementType e = Q->Elements[Q->Front];
  return e;
}
#endif
//////////////////////////
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
//typedef pair<int,int> pii;
//typedef vector<vector<int> > graph;
//const double pi = acos(-1.0);
#define oned(a, x1, x2) { cout << #a << ":"; for(int _i = (x1); _i < (x2); _i++){ cout << " " << a[_i]; } cout << endl; }
#define twod(a, x1, x2, y1, y2) { cout << #a << ":" << endl; for(int _i = (x1); _i < (x2); _i++){ for(int _j = (y1); _j < (y2); _j++){ cout << (_j > y1 ? " " : "") << a[_i][_j]; } cout << endl; } }
#define mp make_pair
#define pb push_back
#define fst first
#define snd second
enum{MAXN = 200005};
int n, m;
vecp g[MAXN];
int vis[MAXN];
int sgn[MAXN];
int val[MAXN];
Queue*Q;
int ans[MAXN];
int cnt;
int comp[MAXN];
int num[MAXN];

void solve(){
    memset(vis,0,sizeof(vis));
    for(int u = 1; u <= n; u++) {
        if(!vis[u]) {
            vis[u] = true;
            sgn[u] = +1;
            val[u] = 0;
            cnt = 0;
            comp[cnt++] = u;
            bool bip = true;
            double x;
            push(Q, u);
            while(!empty(Q)) {
                int v = front(Q); pop(Q);
                for(size_t i = 0; i < g[v].sz; i++){
                    int w   = g[v].ptr[i].fst;
                    int sum = g[v].ptr[i].snd;
                    if(!vis[w]){
                        vis[w] = true;
                        sgn[w] = -sgn[v];
                        val[w] = sum-val[v];
                        comp[cnt++] = w;
                        push(Q, w);
                    }
                    else if(sgn[w]==sgn[v]) {
                        bip = false;
                        x = sgn[w]*(sum-val[w]-val[v])/2;
                    }
                }
            }
            if(bip) {
                for(int i = 0; i < cnt; i++) {
                    int v = comp[i];
                    num[i] = (-sgn[v])*val[v];
                }
                qsort(num, cnt, sizeof(int), cmp);
                x = num[cnt/2];
            }
            for(int i = 0; i < cnt; i++) {
                int v = comp[i];
                ans[v] = val[v] + sgn[v]*x;
            }
            for(int i = 0; i < cnt; i++) {
                int v = comp[i];
                for(size_t i = 0; i < g[v].sz; i++){
                    int w = g[v].ptr[i].fst;
                    if(ans[v]+ans[w]!=g[v].ptr[i].snd){
                        puts("NO");
                        return;
                    }
                }
            }
        }
    }
    puts("YES");
    for(int v = 1; v <= n; v++){
        printf("%.1lf ", 0.5*ans[v]);
    }
    puts("");
}
int main(){
    Q=newQueue();
    while(scanf("%d %d", &n, &m)==2){
        for(int i = 1; i <= n; i++){
            g[i].sz=0;
        }
        for(int i = 0; i < m; i++){
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            c *= 2;
            pbp(g[a], newpair(b,c));
            pbp(g[b], newpair(a,c));
        }
        solve();
    }
    return 0;
}

Compilation message

Graph.c: In function 'main':
Graph.c:243:13: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  243 |             scanf("%d %d %d", &a, &b, &c);
      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB answer = YES
2 Correct 1 ms 1128 KB answer = YES
3 Correct 1 ms 1152 KB answer = YES
4 Correct 1 ms 1152 KB answer = NO
5 Correct 1 ms 1152 KB answer = YES
6 Correct 1 ms 1152 KB answer = YES
7 Correct 1 ms 1152 KB answer = YES
8 Correct 1 ms 1152 KB answer = YES
9 Correct 1 ms 1152 KB answer = NO
10 Correct 1 ms 1152 KB answer = YES
11 Correct 1 ms 1152 KB answer = YES
12 Correct 1 ms 1280 KB answer = NO
13 Correct 1 ms 1152 KB answer = YES
14 Correct 1 ms 1152 KB answer = YES
15 Correct 1 ms 1152 KB answer = YES
16 Correct 1 ms 1152 KB answer = YES
17 Correct 1 ms 1152 KB answer = YES
18 Correct 1 ms 1152 KB answer = YES
19 Correct 1 ms 1152 KB answer = YES
20 Correct 1 ms 1152 KB answer = YES
21 Correct 1 ms 1152 KB answer = YES
22 Correct 1 ms 1152 KB answer = NO
23 Correct 1 ms 1152 KB answer = NO

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB answer = YES
2 Correct 1 ms 1128 KB answer = YES
3 Correct 1 ms 1152 KB answer = YES
4 Correct 1 ms 1152 KB answer = NO
5 Correct 1 ms 1152 KB answer = YES
6 Correct 1 ms 1152 KB answer = YES
7 Correct 1 ms 1152 KB answer = YES
8 Correct 1 ms 1152 KB answer = YES
9 Correct 1 ms 1152 KB answer = NO
10 Correct 1 ms 1152 KB answer = YES
11 Correct 1 ms 1152 KB answer = YES
12 Correct 1 ms 1280 KB answer = NO
13 Correct 1 ms 1152 KB answer = YES
14 Correct 1 ms 1152 KB answer = YES
15 Correct 1 ms 1152 KB answer = YES
16 Correct 1 ms 1152 KB answer = YES
17 Correct 1 ms 1152 KB answer = YES
18 Correct 1 ms 1152 KB answer = YES
19 Correct 1 ms 1152 KB answer = YES
20 Correct 1 ms 1152 KB answer = YES
21 Correct 1 ms 1152 KB answer = YES
22 Correct 1 ms 1152 KB answer = NO
23 Correct 1 ms 1152 KB answer = NO
24 Correct 1 ms 1152 KB answer = YES
25 Correct 1 ms 1152 KB answer = YES
26 Correct 1 ms 1152 KB answer = YES
27 Correct 1 ms 1152 KB answer = YES
28 Correct 1 ms 1152 KB answer = YES
29 Correct 1 ms 1152 KB answer = YES
30 Correct 1 ms 1152 KB answer = NO
31 Correct 1 ms 1152 KB answer = YES
32 Correct 1 ms 1152 KB answer = YES
33 Correct 1 ms 1152 KB answer = YES
34 Correct 1 ms 1152 KB answer = YES
35 Correct 1 ms 1152 KB answer = YES
36 Correct 1 ms 1152 KB answer = YES

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB answer = YES
2 Correct 1 ms 1128 KB answer = YES
3 Correct 1 ms 1152 KB answer = YES
4 Correct 1 ms 1152 KB answer = NO
5 Correct 1 ms 1152 KB answer = YES
6 Correct 1 ms 1152 KB answer = YES
7 Correct 1 ms 1152 KB answer = YES
8 Correct 1 ms 1152 KB answer = YES
9 Correct 1 ms 1152 KB answer = NO
10 Correct 1 ms 1152 KB answer = YES
11 Correct 1 ms 1152 KB answer = YES
12 Correct 1 ms 1280 KB answer = NO
13 Correct 1 ms 1152 KB answer = YES
14 Correct 1 ms 1152 KB answer = YES
15 Correct 1 ms 1152 KB answer = YES
16 Correct 1 ms 1152 KB answer = YES
17 Correct 1 ms 1152 KB answer = YES
18 Correct 1 ms 1152 KB answer = YES
19 Correct 1 ms 1152 KB answer = YES
20 Correct 1 ms 1152 KB answer = YES
21 Correct 1 ms 1152 KB answer = YES
22 Correct 1 ms 1152 KB answer = NO
23 Correct 1 ms 1152 KB answer = NO
24 Correct 1 ms 1152 KB answer = YES
25 Correct 1 ms 1152 KB answer = YES
26 Correct 1 ms 1152 KB answer = YES
27 Correct 1 ms 1152 KB answer = YES
28 Correct 1 ms 1152 KB answer = YES
29 Correct 1 ms 1152 KB answer = YES
30 Correct 1 ms 1152 KB answer = NO
31 Correct 1 ms 1152 KB answer = YES
32 Correct 1 ms 1152 KB answer = YES
33 Correct 1 ms 1152 KB answer = YES
34 Correct 1 ms 1152 KB answer = YES
35 Correct 1 ms 1152 KB answer = YES
36 Correct 1 ms 1152 KB answer = YES
37 Correct 1 ms 1152 KB answer = YES
38 Correct 1 ms 1152 KB answer = YES
39 Correct 1 ms 1152 KB answer = YES
40 Correct 2 ms 1152 KB answer = YES
41 Correct 1 ms 1152 KB answer = NO
42 Correct 2 ms 1152 KB answer = YES
43 Correct 2 ms 1184 KB answer = YES
44 Correct 2 ms 1152 KB answer = YES
45 Correct 2 ms 1152 KB answer = YES
46 Correct 1 ms 1152 KB answer = YES
47 Correct 2 ms 1152 KB answer = YES
48 Correct 2 ms 1152 KB answer = YES

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB answer = YES
2 Correct 1 ms 1128 KB answer = YES
3 Correct 1 ms 1152 KB answer = YES
4 Correct 1 ms 1152 KB answer = NO
5 Correct 1 ms 1152 KB answer = YES
6 Correct 1 ms 1152 KB answer = YES
7 Correct 1 ms 1152 KB answer = YES
8 Correct 1 ms 1152 KB answer = YES
9 Correct 1 ms 1152 KB answer = NO
10 Correct 1 ms 1152 KB answer = YES
11 Correct 1 ms 1152 KB answer = YES
12 Correct 1 ms 1280 KB answer = NO
13 Correct 1 ms 1152 KB answer = YES
14 Correct 1 ms 1152 KB answer = YES
15 Correct 1 ms 1152 KB answer = YES
16 Correct 1 ms 1152 KB answer = YES
17 Correct 1 ms 1152 KB answer = YES
18 Correct 1 ms 1152 KB answer = YES
19 Correct 1 ms 1152 KB answer = YES
20 Correct 1 ms 1152 KB answer = YES
21 Correct 1 ms 1152 KB answer = YES
22 Correct 1 ms 1152 KB answer = NO
23 Correct 1 ms 1152 KB answer = NO
24 Correct 1 ms 1152 KB answer = YES
25 Correct 1 ms 1152 KB answer = YES
26 Correct 1 ms 1152 KB answer = YES
27 Correct 1 ms 1152 KB answer = YES
28 Correct 1 ms 1152 KB answer = YES
29 Correct 1 ms 1152 KB answer = YES
30 Correct 1 ms 1152 KB answer = NO
31 Correct 1 ms 1152 KB answer = YES
32 Correct 1 ms 1152 KB answer = YES
33 Correct 1 ms 1152 KB answer = YES
34 Correct 1 ms 1152 KB answer = YES
35 Correct 1 ms 1152 KB answer = YES
36 Correct 1 ms 1152 KB answer = YES
37 Correct 1 ms 1152 KB answer = YES
38 Correct 1 ms 1152 KB answer = YES
39 Correct 1 ms 1152 KB answer = YES
40 Correct 2 ms 1152 KB answer = YES
41 Correct 1 ms 1152 KB answer = NO
42 Correct 2 ms 1152 KB answer = YES
43 Correct 2 ms 1184 KB answer = YES
44 Correct 2 ms 1152 KB answer = YES
45 Correct 2 ms 1152 KB answer = YES
46 Correct 1 ms 1152 KB answer = YES
47 Correct 2 ms 1152 KB answer = YES
48 Correct 2 ms 1152 KB answer = YES
49 Correct 9 ms 2048 KB answer = YES
50 Correct 9 ms 1920 KB answer = YES
51 Correct 10 ms 2048 KB answer = YES
52 Correct 7 ms 1920 KB answer = NO
53 Correct 2 ms 1280 KB answer = YES
54 Correct 3 ms 1280 KB answer = YES
55 Correct 5 ms 1536 KB answer = YES
56 Correct 9 ms 2176 KB answer = YES
57 Correct 9 ms 2048 KB answer = YES
58 Correct 8 ms 1920 KB answer = YES
59 Correct 9 ms 1792 KB answer = YES
60 Correct 9 ms 1920 KB answer = YES
61 Correct 5 ms 1536 KB answer = YES
62 Correct 120 ms 7160 KB answer = NO
63 Correct 124 ms 7160 KB answer = YES
64 Correct 131 ms 7160 KB answer = NO
65 Correct 121 ms 7160 KB answer = YES
66 Correct 3 ms 1280 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB answer = YES
2 Correct 1 ms 1128 KB answer = YES
3 Correct 1 ms 1152 KB answer = YES
4 Correct 1 ms 1152 KB answer = NO
5 Correct 1 ms 1152 KB answer = YES
6 Correct 1 ms 1152 KB answer = YES
7 Correct 1 ms 1152 KB answer = YES
8 Correct 1 ms 1152 KB answer = YES
9 Correct 1 ms 1152 KB answer = NO
10 Correct 1 ms 1152 KB answer = YES
11 Correct 1 ms 1152 KB answer = YES
12 Correct 1 ms 1280 KB answer = NO
13 Correct 1 ms 1152 KB answer = YES
14 Correct 1 ms 1152 KB answer = YES
15 Correct 1 ms 1152 KB answer = YES
16 Correct 1 ms 1152 KB answer = YES
17 Correct 1 ms 1152 KB answer = YES
18 Correct 1 ms 1152 KB answer = YES
19 Correct 1 ms 1152 KB answer = YES
20 Correct 1 ms 1152 KB answer = YES
21 Correct 1 ms 1152 KB answer = YES
22 Correct 1 ms 1152 KB answer = NO
23 Correct 1 ms 1152 KB answer = NO
24 Correct 1 ms 1152 KB answer = YES
25 Correct 1 ms 1152 KB answer = YES
26 Correct 1 ms 1152 KB answer = YES
27 Correct 1 ms 1152 KB answer = YES
28 Correct 1 ms 1152 KB answer = YES
29 Correct 1 ms 1152 KB answer = YES
30 Correct 1 ms 1152 KB answer = NO
31 Correct 1 ms 1152 KB answer = YES
32 Correct 1 ms 1152 KB answer = YES
33 Correct 1 ms 1152 KB answer = YES
34 Correct 1 ms 1152 KB answer = YES
35 Correct 1 ms 1152 KB answer = YES
36 Correct 1 ms 1152 KB answer = YES
37 Correct 1 ms 1152 KB answer = YES
38 Correct 1 ms 1152 KB answer = YES
39 Correct 1 ms 1152 KB answer = YES
40 Correct 2 ms 1152 KB answer = YES
41 Correct 1 ms 1152 KB answer = NO
42 Correct 2 ms 1152 KB answer = YES
43 Correct 2 ms 1184 KB answer = YES
44 Correct 2 ms 1152 KB answer = YES
45 Correct 2 ms 1152 KB answer = YES
46 Correct 1 ms 1152 KB answer = YES
47 Correct 2 ms 1152 KB answer = YES
48 Correct 2 ms 1152 KB answer = YES
49 Correct 9 ms 2048 KB answer = YES
50 Correct 9 ms 1920 KB answer = YES
51 Correct 10 ms 2048 KB answer = YES
52 Correct 7 ms 1920 KB answer = NO
53 Correct 2 ms 1280 KB answer = YES
54 Correct 3 ms 1280 KB answer = YES
55 Correct 5 ms 1536 KB answer = YES
56 Correct 9 ms 2176 KB answer = YES
57 Correct 9 ms 2048 KB answer = YES
58 Correct 8 ms 1920 KB answer = YES
59 Correct 9 ms 1792 KB answer = YES
60 Correct 9 ms 1920 KB answer = YES
61 Correct 5 ms 1536 KB answer = YES
62 Correct 120 ms 7160 KB answer = NO
63 Correct 124 ms 7160 KB answer = YES
64 Correct 131 ms 7160 KB answer = NO
65 Correct 121 ms 7160 KB answer = YES
66 Correct 3 ms 1280 KB answer = YES
67 Correct 86 ms 9712 KB answer = YES
68 Correct 78 ms 9552 KB answer = YES
69 Correct 72 ms 9080 KB answer = YES
70 Correct 113 ms 12792 KB answer = YES
71 Correct 70 ms 9084 KB answer = YES
72 Correct 111 ms 9968 KB answer = YES
73 Correct 103 ms 9464 KB answer = YES
74 Correct 61 ms 6392 KB answer = YES
75 Correct 43 ms 6376 KB answer = NO
76 Correct 12 ms 2304 KB answer = YES
77 Correct 22 ms 3328 KB answer = YES
78 Correct 40 ms 4944 KB answer = YES
79 Correct 91 ms 8624 KB answer = YES
80 Correct 67 ms 6776 KB answer = YES
81 Correct 61 ms 8696 KB answer = NO
82 Correct 96 ms 9208 KB answer = YES
83 Correct 112 ms 9336 KB answer = YES
84 Correct 118 ms 9756 KB answer = YES
85 Correct 85 ms 9592 KB answer = YES
86 Correct 79 ms 9208 KB answer = YES
87 Correct 75 ms 8824 KB answer = NO
88 Correct 121 ms 9084 KB answer = YES
89 Correct 84 ms 8696 KB answer = YES
90 Correct 84 ms 8696 KB answer = YES
91 Correct 101 ms 8696 KB answer = YES
92 Correct 44 ms 5368 KB answer = YES
93 Correct 47 ms 5372 KB answer = YES
94 Correct 88 ms 9080 KB answer = NO
95 Correct 59 ms 8312 KB answer = NO
96 Correct 189 ms 12672 KB answer = YES
97 Correct 56 ms 9080 KB answer = NO