oj.uz

Submission #425535

# Submission time Handle Problem Language Result Execution time Memory
425535 2021-06-13T06:40:33 Z Charis02 Ancient Books (IOI17_books) C++14
0 / 100
 11 ms 6988 KB 
#include "books.h"
#include<iostream>
#include<vector>
#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 100003
#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;

    //    cout << "here " << cur.second << endl;

        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;
}

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;
}

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

            int dist = abso(i-j);
         //   cout << "here " << i << " " << j << "   " << dist << " " << id[i] << " " << id[j] << endl;

            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;
    }

  //  cout << ans << endl;

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

	return ans;
}

Compilation message

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

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 4 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Incorrect 2 ms 2636 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 4 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Incorrect 2 ms 2636 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 4 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Incorrect 2 ms 2636 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 6988 KB 3rd lines differ - on the 1st token, expected: '3304', found: '4322'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 4 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Incorrect 2 ms 2636 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -