Submission #425570

#	Time	Username	Problem	Language	Result	Execution time	Memory
425570		Charis02	Ancient Books (IOI17_books)	C++14	50 / 100	269 ms	60632 KiB

books

#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 1000003
#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));
}

ll calculate_weights(const vector < int >&p,const vector < vector < int > >&cycles)
{
    edges.clear();
    vector < pi > ranges;

    rep(i,0,cycles.size())
    {
        ranges.push_back(mp(cycles[i][0],cycles[i][0]));

        rep(j,0,cycles[i].size())
        {
            ll v = cycles[i][j];
            ll pv = p[v];
            ranges[i].first = min(ranges[i].first,v);
            ranges[i].first = min(ranges[i].first,pv);
            ranges[i].second = max(ranges[i].second,v);
            ranges[i].second = max(ranges[i].second,pv);
        }
    }

    sort(ranges.begin(),ranges.end());
    vector < pi > nranges;

    ll curlow = ranges[0].first;
    ll curhigh = ranges[0].second;

    rep(i,1,ranges.size())
    {
        if(ranges[i].first > curhigh)
        {
            nranges.push_back(mp(curlow,curhigh));
            curlow = ranges[i].first;
            curhigh = ranges[i].second;
        }
        else
            curhigh = max(ranges[i].second,curhigh);
    }

    nranges.push_back(mp(curlow,curhigh));

    ll res = 0;

    rep(i,1,nranges.size())
    {
        res += nranges[i].first-nranges[i-1].second;
    }

    return res*2;
}

long long minimum_walk(std::vector<int> p, int s)
{
    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;
    }

    ans += calculate_weights(p,cycles);

	return ans;
}

Compilation message (stderr)

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())
      |     ^~~
books.cpp: In function 'long long int calculate_weights(const std::vector<int>&, const std::vector<std::vector<int> >&)':
books.cpp:8:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define rep(i,a,b) for(int i = a;i < b;i++)
......
  146 |     rep(i,0,cycles.size())
      |         ~~~~~~~~~~~~~~~~~           
books.cpp:146:5: note: in expansion of macro 'rep'
  146 |     rep(i,0,cycles.size())
      |     ^~~
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++)
......
  150 |         rep(j,0,cycles[i].size())
      |             ~~~~~~~~~~~~~~~~~~~~    
books.cpp:150:9: note: in expansion of macro 'rep'
  150 |         rep(j,0,cycles[i].size())
      |         ^~~
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++)
......
  167 |     rep(i,1,ranges.size())
      |         ~~~~~~~~~~~~~~~~~           
books.cpp:167:5: note: in expansion of macro 'rep'
  167 |     rep(i,1,ranges.size())
      |     ^~~
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++)
......
  183 |     rep(i,1,nranges.size())
      |         ~~~~~~~~~~~~~~~~~~          
books.cpp:183:5: note: in expansion of macro 'rep'
  183 |     rep(i,1,nranges.size())
      |     ^~~

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30