Submission #436953

#	Time	Username	Problem	Language	Result	Execution time	Memory
436953		idas	Cheap flights (LMIO18_pigus_skrydziai)	C++11	0 / 100	604 ms	39932 KiB

pigus_skrydziai

#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i = (begin); i < (end); i++)
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define F first
#define S second
#define PB push_back
#define MP make_pair

using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long long ll;

void setIO()
{
    FAST_IO;
}

const int N=3e5+100, M=5e5+100;

int n, m, cnt[N];
vector<pii> ad[N];

bool vis[M], b[N];
map<pii, int> conv;

void dfs(int u)
{
    b[u] = true;
    for(auto it : ad[u])
    {
        int v=it.F, w=it.S;
        /*if(!vis[conv[MP(min(u, v), max(u, v))]])
        {
            cnt[u]+=w;
            cnt[v]+=w;
            vis[conv[MP(min(u, v), max(u, v))]]=true;
        }*/
        cnt[u]+=w;
        cnt[v]+=w;
        if(!b[v])
            dfs(v);
    }
}

int main()
{
    setIO();
    cin >> n >> m;
    FOR(i, 0, m)
    {
        int a, b, c;
        cin >> a >> b >> c;
        conv[MP(min(a, b), max(a, b))]=i;
        ad[a-1].PB(MP(b-1, c));
        ad[b-1].PB(MP(a-1, c));
    }
    dfs(0);
    int mx=-1;
    FOR(i, 0, n) mx=max(mx, cnt[i]);
    cout << mx/2;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 25
• Subtask 3: 0 / 16
• Subtask 4: 0 / 47