Submission #1030366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030366		8pete8	Teleporters (IOI08_teleporters)	C++17	100 / 100	230 ms	50408 KiB

teleporters

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
//#define int long long
using namespace std;
const int mod=998244353,mxn=2e6+5,inf=1e9,minf=-1e9,lg=25;
int n,m,k,x,y;
int dp[mxn+10],vis[mxn+10];
pii nxt[mxn+10];
int cnt=0;
void dfs(int cur){
    //memory?
    while(!vis[cur]){
        vis[cur]=1;
        if(vis[nxt[cur].f])return;
        cnt+=nxt[cur].s;
        cur=nxt[cur].f;
    }
    /*
    if(vis[cur])return;
    vis[cur]=1;
    if(!vis[nxt[cur].f])dfs(nxt[cur].f),dp[cur]=dp[nxt[cur].f]+nxt[cur].s;*/
}
int32_t main(){
    fastio
    cin>>n>>m;
    for(int i=0;i<=mxn;i++)dp[i]=0,nxt[i]={i+1,0};
    for(int i=0;i<n;i++){
        int a,b;cin>>a>>b;
        nxt[a]={b+1,1},nxt[b]={a+1,1};
    }
    vis[mxn+1]=1;
    cnt=0;
    dfs(1);
    int ans=cnt;
    vector<int>have;
    for(int i=1;i<=mxn;i++)if(!vis[i]){//comp
        cnt=0;
        dfs(i),have.pb(cnt);
    }
    sort(rall(have));
    for(int i=0;i<have.size()&&m>0;i++)m--,ans+=(3+have[i]);
    //other
    if(m%2)ans++,m--;
    ans+=(m*2);
    cout<<ans<<'\n';
}
/*
putting a new teleporter down allow us to repeat any part of the sequence even if its not on the orignial path
a1 b1 X a2 b2 (order of teleportation a1->a2->b2->b1->X->a2->a1->b1->b2)
a1 b1 c1 X a2 b2 c2 (a1,a2,b2,b1,c1,c2....) odd number teleporter wont do anything
a1 b1 c1 d1 X a2 b2 c2 d2
a1,a2,b2,b1,c1,c2,d2,d1,X,a2,a1,b1,b2,c2,c1,d1,d2 
with 4 or 2 it will execute X 1 times
put m tp(m is even)
cost+=(X+(2*m))
not original path{
    can split in comp?
    if its not used in orginal path then it has to be covered by some range l(X)r where no range is sticking out of it
    if we put teleporter after l (x,r,l,tpback)
    we can only put 1 tp for each comp
    cost+=3+length
}
sort all comp
*/

Compilation message (stderr)

teleporters.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
teleporters.cpp:40:17: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   40 | void dfs(int cur){
      |                 ^
teleporters.cpp:53:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   53 | int32_t main(){
      |              ^
teleporters.cpp: In function 'int32_t main()':
teleporters.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i=0;i<have.size()&&m>0;i++)m--,ans+=(3+have[i]);
      |                 ~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5