oj.uz

Submission #425561

# Submission time Handle Problem Language Result Execution time Memory
425561 2021-06-13T07:15:11 Z Charis02 Ancient Books (IOI17_books) C++14
22 / 100
 156 ms 29408 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)
{
    if(a.first>a.second)
        swap(a.first,a.second);
    if(b.first>b.second)
        swap(b.first,b.second);
    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;

            ll 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();
    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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 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 1 ms 204 KB Output is correct
14 Correct 1 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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 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 1 ms 204 KB Output is correct
14 Correct 1 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 71 ms 23920 KB Output is correct
20 Correct 50 ms 21848 KB Output is correct
21 Correct 2 ms 328 KB Output is correct
22 Correct 24 ms 7244 KB Output is correct
23 Correct 28 ms 12412 KB Output is correct
24 Correct 49 ms 16140 KB Output is correct
25 Correct 75 ms 23424 KB Output is correct
26 Correct 101 ms 29292 KB Output is correct
27 Correct 101 ms 29408 KB Output is correct
28 Correct 102 ms 28908 KB Output is correct
29 Correct 28 ms 12452 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 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 1 ms 204 KB Output is correct
14 Correct 1 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 71 ms 23920 KB Output is correct
20 Correct 50 ms 21848 KB Output is correct
21 Correct 2 ms 328 KB Output is correct
22 Correct 24 ms 7244 KB Output is correct
23 Correct 28 ms 12412 KB Output is correct
24 Correct 49 ms 16140 KB Output is correct
25 Correct 75 ms 23424 KB Output is correct
26 Correct 101 ms 29292 KB Output is correct
27 Correct 101 ms 29408 KB Output is correct
28 Correct 102 ms 28908 KB Output is correct
29 Correct 28 ms 12452 KB Output is correct
30 Runtime error 156 ms 16256 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 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 1 ms 204 KB Output is correct
14 Correct 1 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 71 ms 23920 KB Output is correct
20 Correct 50 ms 21848 KB Output is correct
21 Correct 2 ms 328 KB Output is correct
22 Correct 24 ms 7244 KB Output is correct
23 Correct 28 ms 12412 KB Output is correct
24 Correct 49 ms 16140 KB Output is correct
25 Correct 75 ms 23424 KB Output is correct
26 Correct 101 ms 29292 KB Output is correct
27 Correct 101 ms 29408 KB Output is correct
28 Correct 102 ms 28908 KB Output is correct
29 Correct 28 ms 12452 KB Output is correct
30 Runtime error 156 ms 16256 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -