Submission #842552


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

struct edge{int to,cost,id;};

vector<edge> G[100];
int C[100][100]={0};

int main()
{
    int n,m,k;
    cin >>n >>m >>k;
    rep(i,m)
    {
        int f,t,c;
        cin >>f >>t >>c;
        --f;
        --t;
        G[f].pb(edge{t,c,i});
        G[t].pb(edge{f,c,i});
        C[f][t]=C[t][f]=c;
    }

    int g=0;

    //閉路に含まれない辺,含まれる辺
    vector<int> x,y;

    vector<bool> vis(n);
    vector<bool> use(m);
    vector<int> par(n,-1);
    rep(i,n)
    {
        if(vis[i]) continue;
        ++g;
        vis[i]=true;
        par[i]=i;

        int viscount=1;
        int va=-1, vb=-1;
        vector<int> cost, dist(n,0);
        queue<int> que;
        que.push(i);
        while(!que.empty())
        {
            int v=que.front();
            que.pop();
            rep(j,G[v].size())
            {
                edge e=G[v][j];
                int nx=e.to;
                if(!use[e.id])
                {
                    use[e.id]=true;
                    cost.pb(e.cost);
                    if(!vis[nx])
                    {
                        vis[nx]=true;
                        que.push(nx);
                        dist[nx]=dist[v]+1;
                        par[nx]=v;
                        ++viscount;
                    }
                    else
                    {
                        va=v;
                        vb=nx;
                        y.pb(e.cost);
                    }
                }
            }
        }

        int COST=cost.size();
        if(viscount==COST)
        {
            //閉路あり
            if(dist[va]>dist[vb])
            {
                while(dist[va]>dist[vb])
                {
                    y.pb(C[va][par[va]]);
                    va=par[va];
                }
            }
            if(dist[va]<dist[vb])
            {
                while(dist[va]<dist[vb])
                {
                    y.pb(C[vb][par[vb]]);
                    vb=par[vb];
                }
            }

            while(va!=vb)
            {
                y.pb(C[va][par[va]]);
                y.pb(C[vb][par[vb]]);
                va=par[va];
                vb=par[vb];
            }

            sort(all(cost));
            sort(all(y));
            int yidx=0;
            rep(cidx,COST)
            {
                if(cost[cidx]==y[yidx]) ++yidx;
                else x.pb(cost[cidx]);
            }
        }
        else for(auto &c:cost) x.pb(c);
    }

    sort(all(x));
    sort(all(y));

    // printf("X,Y %d, %d\n", x.size(), y.size());

    int ans=0;
    if(g<k)
    {
        ans=123456789;
        if(k-g<=x.size())
        {
            int tmp=0;
            rep(i,k-g) tmp+=x[i];
            ans=min(ans,tmp);
        }

        if(y.size()>=3)
        {
            int tmp=y[0]+y[1];

            vector<int> z(x);
            for(int i=2; i<y.size(); ++i) z.pb(y[i]);
            sort(all(z));
            rep(i,k-g-1) tmp+=z[i];

            ans=min(ans,tmp);
        }
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task E - 独立記念日
User imulan
Language C++11 (GCC 4.8.1)
Score 100
Code Size 3513 Byte
Status AC
Exec Time 34 ms
Memory 1288 KB

Judge Result

Set Name nonloop loop
Score / Max Score 30 / 30 70 / 70
Status
AC × 34
AC × 66
Set Name Test Cases
nonloop nonloop/case_000.txt, nonloop/case_001.txt, nonloop/case_002.txt, nonloop/case_003.txt, nonloop/case_004.txt, nonloop/case_005.txt, nonloop/case_006.txt, nonloop/case_007.txt, nonloop/case_008.txt, nonloop/case_009.txt, nonloop/case_010.txt, nonloop/case_011.txt, nonloop/case_012.txt, nonloop/case_013.txt, nonloop/case_014.txt, nonloop/case_015.txt, nonloop/case_016.txt, nonloop/case_017.txt, nonloop/case_018.txt, nonloop/case_019.txt, nonloop/case_020.txt, nonloop/case_021.txt, nonloop/case_022.txt, nonloop/case_023.txt, nonloop/case_024.txt, nonloop/case_025.txt, nonloop/case_026.txt, nonloop/case_027.txt, nonloop/case_028.txt, nonloop/case_029.txt, nonloop/case_030.txt, nonloop/case_031.txt, nonloop/case_032.txt, nonloop/case_033.txt
loop loop/case_000.txt, loop/case_001.txt, loop/case_002.txt, loop/case_003.txt, loop/case_004.txt, loop/case_005.txt, loop/case_006.txt, loop/case_007.txt, loop/case_008.txt, loop/case_009.txt, loop/case_010.txt, loop/case_011.txt, loop/case_012.txt, loop/case_013.txt, loop/case_014.txt, loop/case_015.txt, loop/case_016.txt, loop/case_017.txt, loop/case_018.txt, loop/case_019.txt, loop/case_020.txt, loop/case_021.txt, loop/case_022.txt, loop/case_023.txt, loop/case_024.txt, loop/case_025.txt, loop/case_026.txt, loop/case_027.txt, loop/case_028.txt, loop/case_029.txt, loop/case_030.txt, loop/case_031.txt, loop/case_032.txt, loop/case_033.txt, loop/loop_case_000.txt, loop/loop_case_001.txt, loop/loop_case_002.txt, loop/loop_case_003.txt, loop/loop_case_004.txt, loop/loop_case_005.txt, loop/loop_case_006.txt, loop/loop_case_007.txt, loop/loop_case_008.txt, loop/loop_case_009.txt, loop/loop_case_010.txt, loop/loop_case_011.txt, loop/loop_case_012.txt, loop/loop_case_013.txt, loop/loop_case_014.txt, loop/loop_case_015.txt, loop/loop_case_016.txt, loop/loop_case_017.txt, loop/loop_case_018.txt, loop/loop_case_019.txt, loop/loop_case_020.txt, loop/loop_case_021.txt, loop/loop_case_022.txt, loop/loop_case_023.txt, loop/loop_case_024.txt, loop/loop_case_025.txt, loop/loop_case_026.txt, loop/loop_case_027.txt, loop/loop_case_028.txt, loop/loop_case_029.txt, loop/loop_case_030.txt, loop/loop_case_031.txt
Case Name Status Exec Time Memory
loop/case_000.txt AC 34 ms 1100 KB
loop/case_001.txt AC 28 ms 1168 KB
loop/case_002.txt AC 29 ms 1156 KB
loop/case_003.txt AC 30 ms 1148 KB
loop/case_004.txt AC 29 ms 1156 KB
loop/case_005.txt AC 29 ms 1172 KB
loop/case_006.txt AC 27 ms 1152 KB
loop/case_007.txt AC 28 ms 1136 KB
loop/case_008.txt AC 33 ms 1160 KB
loop/case_009.txt AC 31 ms 1100 KB
loop/case_010.txt AC 28 ms 1228 KB
loop/case_011.txt AC 31 ms 1172 KB
loop/case_012.txt AC 29 ms 1172 KB
loop/case_013.txt AC 29 ms 1172 KB
loop/case_014.txt AC 31 ms 1224 KB
loop/case_015.txt AC 30 ms 1164 KB
loop/case_016.txt AC 30 ms 1172 KB
loop/case_017.txt AC 28 ms 1228 KB
loop/case_018.txt AC 30 ms 1168 KB
loop/case_019.txt AC 30 ms 1172 KB
loop/case_020.txt AC 29 ms 1160 KB
loop/case_021.txt AC 28 ms 1156 KB
loop/case_022.txt AC 29 ms 1156 KB
loop/case_023.txt AC 28 ms 1156 KB
loop/case_024.txt AC 30 ms 1136 KB
loop/case_025.txt AC 29 ms 1252 KB
loop/case_026.txt AC 29 ms 1160 KB
loop/case_027.txt AC 30 ms 1168 KB
loop/case_028.txt AC 29 ms 1136 KB
loop/case_029.txt AC 26 ms 1176 KB
loop/case_030.txt AC 30 ms 1176 KB
loop/case_031.txt AC 27 ms 1176 KB
loop/case_032.txt AC 28 ms 1160 KB
loop/case_033.txt AC 29 ms 1236 KB
loop/loop_case_000.txt AC 28 ms 1164 KB
loop/loop_case_001.txt AC 29 ms 1176 KB
loop/loop_case_002.txt AC 29 ms 1180 KB
loop/loop_case_003.txt AC 27 ms 1160 KB
loop/loop_case_004.txt AC 28 ms 1176 KB
loop/loop_case_005.txt AC 27 ms 1148 KB
loop/loop_case_006.txt AC 28 ms 1180 KB
loop/loop_case_007.txt AC 28 ms 1172 KB
loop/loop_case_008.txt AC 28 ms 1176 KB
loop/loop_case_009.txt AC 28 ms 1160 KB
loop/loop_case_010.txt AC 28 ms 1176 KB
loop/loop_case_011.txt AC 28 ms 1160 KB
loop/loop_case_012.txt AC 29 ms 1160 KB
loop/loop_case_013.txt AC 28 ms 1164 KB
loop/loop_case_014.txt AC 28 ms 1176 KB
loop/loop_case_015.txt AC 30 ms 1176 KB
loop/loop_case_016.txt AC 29 ms 1160 KB
loop/loop_case_017.txt AC 26 ms 1172 KB
loop/loop_case_018.txt AC 30 ms 1176 KB
loop/loop_case_019.txt AC 29 ms 1128 KB
loop/loop_case_020.txt AC 28 ms 1160 KB
loop/loop_case_021.txt AC 29 ms 1092 KB
loop/loop_case_022.txt AC 30 ms 1232 KB
loop/loop_case_023.txt AC 29 ms 1288 KB
loop/loop_case_024.txt AC 30 ms 1224 KB
loop/loop_case_025.txt AC 30 ms 1236 KB
loop/loop_case_026.txt AC 30 ms 1132 KB
loop/loop_case_027.txt AC 29 ms 1164 KB
loop/loop_case_028.txt AC 28 ms 1236 KB
loop/loop_case_029.txt AC 29 ms 1152 KB
loop/loop_case_030.txt AC 28 ms 1164 KB
loop/loop_case_031.txt AC 28 ms 1164 KB
nonloop/case_000.txt AC 28 ms 1176 KB
nonloop/case_001.txt AC 28 ms 1168 KB
nonloop/case_002.txt AC 28 ms 1176 KB
nonloop/case_003.txt AC 27 ms 1172 KB
nonloop/case_004.txt AC 26 ms 1168 KB
nonloop/case_005.txt AC 30 ms 1160 KB
nonloop/case_006.txt AC 31 ms 1172 KB
nonloop/case_007.txt AC 28 ms 1160 KB
nonloop/case_008.txt AC 29 ms 1176 KB
nonloop/case_009.txt AC 28 ms 1172 KB
nonloop/case_010.txt AC 30 ms 1228 KB
nonloop/case_011.txt AC 29 ms 1180 KB
nonloop/case_012.txt AC 28 ms 1164 KB
nonloop/case_013.txt AC 27 ms 1176 KB
nonloop/case_014.txt AC 29 ms 1136 KB
nonloop/case_015.txt AC 29 ms 1260 KB
nonloop/case_016.txt AC 28 ms 1160 KB
nonloop/case_017.txt AC 27 ms 1164 KB
nonloop/case_018.txt AC 29 ms 1180 KB
nonloop/case_019.txt AC 28 ms 1176 KB
nonloop/case_020.txt AC 29 ms 1164 KB
nonloop/case_021.txt AC 28 ms 1160 KB
nonloop/case_022.txt AC 29 ms 1176 KB
nonloop/case_023.txt AC 29 ms 1172 KB
nonloop/case_024.txt AC 26 ms 1168 KB
nonloop/case_025.txt AC 29 ms 1256 KB
nonloop/case_026.txt AC 29 ms 1144 KB
nonloop/case_027.txt AC 28 ms 1164 KB
nonloop/case_028.txt AC 28 ms 1152 KB
nonloop/case_029.txt AC 29 ms 1160 KB
nonloop/case_030.txt AC 34 ms 1168 KB
nonloop/case_031.txt AC 29 ms 1176 KB
nonloop/case_032.txt AC 29 ms 1232 KB
nonloop/case_033.txt AC 29 ms 1164 KB