Submission #1684778


Source Code Expand

Copy
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stdio.h>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ll long long

//ノードのコストを管理
typedef struct {
    int edge_cnt;
} Node;

//辺の長さとその繋いでいるものを管理
typedef struct {
    int from;
    int to;
    int del;
} Edge;


int main()
{
    int N, M, is_updated = 0;
    cin >> N >> M;

    Node nodes[50];
    Edge edges[200];
    REP(i, N) 
    {
        nodes[i].edge_cnt = 0;
    }
    REP(i, M) 
    {
        cin >> edges[i].from >> edges[i].to;
        edges[i].del = 0;
        nodes[edges[i].from - 1].edge_cnt++;
        nodes[edges[i].to - 1].edge_cnt++;
    } 

    int cnt = 0;
    do 
    {
        is_updated = 0;
        REP(i, M) 
        {
            if(edges[i].del == 1) continue;
            if(nodes[edges[i].from - 1].edge_cnt == 1 || nodes[edges[i].to - 1].edge_cnt == 1)
            {
                edges[i].del = 1;
                nodes[edges[i].from - 1].edge_cnt--;
                nodes[edges[i].to - 1].edge_cnt--;
                cnt++;
                is_updated = 1;
            }
        }
    } 
    while(is_updated);

    cout << cnt << endl;

}

Submission Info

Submission Time
Task C - Bridge
User shira
Language C++14 (GCC 5.4.1)
Score 300
Code Size 1336 Byte
Status
Exec Time 1 ms
Memory 256 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
All 300 / 300 sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
subtask_1_1.txt 1 ms 256 KB
subtask_1_10.txt 1 ms 256 KB
subtask_1_11.txt 1 ms 256 KB
subtask_1_12.txt 1 ms 256 KB
subtask_1_13.txt 1 ms 256 KB
subtask_1_14.txt 1 ms 256 KB
subtask_1_15.txt 1 ms 256 KB
subtask_1_16.txt 1 ms 256 KB
subtask_1_17.txt 1 ms 256 KB
subtask_1_2.txt 1 ms 256 KB
subtask_1_3.txt 1 ms 256 KB
subtask_1_4.txt 1 ms 256 KB
subtask_1_5.txt 1 ms 256 KB
subtask_1_6.txt 1 ms 256 KB
subtask_1_7.txt 1 ms 256 KB
subtask_1_8.txt 1 ms 256 KB
subtask_1_9.txt 1 ms 256 KB