oj.uz

답안 #425555

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
425555 2021-06-13T07:08:12 Z Charis02 고대 책들 (IOI17_books) C++14
22 / 100
 134 ms 29444 KB 
#include "books.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#define ll long long
#define pi pair < ll,ll >
#define rep(i,a,b) for(int i = a;i < b;i++)
#define mp(a,b) make_pair(a,b)
#define N 1003
#define INF 1e9+7

using namespace std;

vector < pi > graph[N];
int id[N];
bool vis[N];

ll abso(ll x)
{
    return (x < 0) ? -x : x;
}

ll dijkstra_weight(int n,int source)
{
    ll d[n];
    ll w[n];

    rep(i,0,n)
        d[i] = INF;

    d[source] = 0;
    w[source]=0;
    priority_queue < pi > pq;
    pq.push(mp(0,source));

    while(!pq.empty())
    {
        pi cur = pq.top();
        pq.pop();

        cur.first*=-1;

        if(cur.first > d[cur.second])
            continue;

        rep(i,0,graph[cur.second].size())
        {
            int v = graph[cur.second][i].first;
            ll wv = graph[cur.second][i].second;

          //  cout <<"in " << v << endl;

            if(d[v] > cur.first + wv)
            {
                d[v]=cur.first+wv;
                w[v]=wv;
                pq.push(mp(-d[v],v));
            }
        }
    }

    ll res = 0;

    rep(i,0,n)
    {
        res += w[i];
    }

    return 2*res;
}

int dsu[N];
vector < pair < ll,pi > > edges;
int f(int x)
{
    if(dsu[x]==x)
        return x;
    return dsu[x]=f(dsu[x]);
}
bool issameset(int x,int y)
{
    return f(x)==f(y);
}

void join(int x,int y)
{
    dsu[f(x)]=f(y);
    return;
}

ll mst_weight(int n,int source)
{
    rep(i,0,n)
        dsu[i]=i;
    ll res = 0;
    sort(edges.begin(),edges.end());

    rep(i,0,edges.size())
    {
        int u = edges[i].second.first;
        int v = edges[i].second.second;
        ll w = edges[i].first;

        if(!issameset(u,v))
        {
            join(u,v);
            res+=2*w;
        }
    }

    return res;
}

ll get_cycle_cost(vector < int > c)
{
    if(c.size()==1)
        return 0;

    ll res = 0;

    rep(i,1,c.size())
    {
        res += abso(c[i]-c[i-1]);
    }

    res += abso(c[0]-c[c.size()-1]);

    return res;
}

ll get_distance(pi a,pi b)
{
    return max((ll)0,max(a.first,b.first)-min(a.second,b.second));
}

void calculate_weights(int n,const vector < int > &p)
{
    rep(i,0,n)
    {
        rep(j,i+1,n)
        {
            if(!vis[i] || !vis[j] || id[i] == id[j])
                continue;

            int dist = get_distance(mp(i,p[i]),mp(j,p[j]));
            edges.push_back(mp(dist,mp(id[i],id[j])));
            graph[id[i]].push_back(mp(id[j],dist));
            graph[id[j]].push_back(mp(id[i],dist));
        }
    }

    return;
}

long long minimum_walk(std::vector<int> p, int s) // for 1st sub
{
    int n = p.size();

    rep(i,0,n)
    {
        graph[i].clear();
        vis[i]=false;
        id[i] = -1;
    }
    vector < vector < int > > cycles;
    ll ans = 0;

    rep(i,0,n)
    {
        if(p[i] == i || vis[i])
            continue;

        int cur = i;
        int ind = cycles.size();
        cycles.push_back(vector < int > ());

        while(!vis[cur])
        {
            id[cur] = ind;
            vis[cur] = true;
            cycles[ind].push_back(cur);
            cur = p[cur];
        }

        ans += get_cycle_cost(cycles[ind]);
    }

    if(!vis[s])
    {
        vis[s]=true;
        int ind = cycles.size();
        cycles.push_back(vector < int > ());
        cycles[ind].push_back(s);
        id[s] = ind;
    }

    calculate_weights(n,p);
    ans += mst_weight(cycles.size(),id[s]);

	return ans;
}

Compilation message

books.cpp: In function 'long long int dijkstra_weight(int, int)':
books.cpp:8:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define rep(i,a,b) for(int i = a;i < b;i++)
......
   47 |         rep(i,0,graph[cur.second].size())
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
books.cpp:47:9: note: in expansion of macro 'rep'
   47 |         rep(i,0,graph[cur.second].size())
      |         ^~~
books.cpp: In function 'long long int mst_weight(int, int)':
books.cpp:8:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define rep(i,a,b) for(int i = a;i < b;i++)
......
   99 |     rep(i,0,edges.size())
      |         ~~~~~~~~~~~~~~~~            
books.cpp:99:5: note: in expansion of macro 'rep'
   99 |     rep(i,0,edges.size())
      |     ^~~
books.cpp: In function 'long long int get_cycle_cost(std::vector<int>)':
books.cpp:8:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define rep(i,a,b) for(int i = a;i < b;i++)
......
  122 |     rep(i,1,c.size())
      |         ~~~~~~~~~~~~                
books.cpp:122:5: note: in expansion of macro 'rep'
  122 |     rep(i,1,c.size())
      |     ^~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 73 ms 23992 KB Output is correct
20 Correct 63 ms 21812 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 24 ms 7288 KB Output is correct
23 Correct 28 ms 12412 KB Output is correct
24 Correct 52 ms 16240 KB Output is correct
25 Correct 64 ms 23408 KB Output is correct
26 Correct 102 ms 29352 KB Output is correct
27 Correct 93 ms 29444 KB Output is correct
28 Correct 92 ms 28908 KB Output is correct
29 Correct 33 ms 12424 KB Output is correct

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 73 ms 23992 KB Output is correct
20 Correct 63 ms 21812 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 24 ms 7288 KB Output is correct
23 Correct 28 ms 12412 KB Output is correct
24 Correct 52 ms 16240 KB Output is correct
25 Correct 64 ms 23408 KB Output is correct
26 Correct 102 ms 29352 KB Output is correct
27 Correct 93 ms 29444 KB Output is correct
28 Correct 92 ms 28908 KB Output is correct
29 Correct 33 ms 12424 KB Output is correct
30 Runtime error 134 ms 17544 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 6908 KB 3rd lines differ - on the 1st token, expected: '3304', found: '2744'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 73 ms 23992 KB Output is correct
20 Correct 63 ms 21812 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 24 ms 7288 KB Output is correct
23 Correct 28 ms 12412 KB Output is correct
24 Correct 52 ms 16240 KB Output is correct
25 Correct 64 ms 23408 KB Output is correct
26 Correct 102 ms 29352 KB Output is correct
27 Correct 93 ms 29444 KB Output is correct
28 Correct 92 ms 28908 KB Output is correct
29 Correct 33 ms 12424 KB Output is correct
30 Runtime error 134 ms 17544 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -