oj.uz

Submission #1038215

# Submission time Handle Problem Language Result Execution time Memory
1038215 2024-07-29T14:26:33 Z aymanrs Longest Trip (IOI23_longesttrip) C++17
5 / 100
 11 ms 596 KB 
#include "longesttrip.h"
#include <bits/stdc++.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
char g[256][256] = {{0}};
bool ej[256] = {false};
bool isg(int a, int b){
    if(g[a][b]) {
        return g[a][b] == 1;
    }
    if(are_connected({a},{b})){
        g[a][b]=g[b][a]=1;
        return true;
    }
    g[a][b]=g[b][a]=-1;
    return false;
}
bool arc(const vector<int>& a, const vector<int>& b){
    if(a.empty()||b.empty()) return false;
    bool at0=false;
    for(int i : a) for(int j : b) {
        if(g[i][j]==1) return true;
        else if(!g[i][j]) at0=true;
    }
    if(!at0) return false;
    return are_connected(a, b);
}
pair<vector<int>,vector<int>> fl(const vector<int>& V){
    if(V.size()<=1) return {V, {}};
    memset(ej, 0, sizeof(ej));
    int i, j;
    vector<int> a;a.push_back(V[0]);
    for(i = 1;i < V.size();i++){
        if(!g[a.back()][V[i]]){
            if(isg(a.back(), V[i])){
                a.push_back(V[i]);
            } else {
                j = a.back();
                break;
            }
        }
    }
    if(a.size() == V.size()) return {a, {}};
    vector<int> b, c;
    a.clear();
    i=V[i];j=V[j];
    for(int k : V){
        if(k==i||k==j) continue;
        if(!isg(k,j)) a.push_back(k);
        else if(!isg(k,i)) c.push_back(k);
        else {
            b.push_back(k);
        }
    }
    if(b.empty()){
        if(!arc(a,c)) {
            a.push_back(i);
            c.push_back(j);
            return {a,c};
        }
        int l=0,r=c.size()-1, ll=0,rr=a.size()-1;
        while(l<r&&ll<rr){
            if(r-l > rr-ll){
                int m = r+l>>1;
                if(arc(vector<int>{c.begin()+l,c.begin()+m+1}, vector<int>{a.begin()+ll,a.begin()+rr+1})){
                    r=m;
                } else l = m+1;
            } else {
                int m = ll+rr>>1;
                if(arc(vector<int>{c.begin()+l,c.begin()+r+1}, vector<int>{a.begin()+ll,a.begin()+m+1})){
                    rr=m;
                } else ll = m+1;
            }
        }
        a.push_back(i);swap(a[ll], a.back());
        c.push_back(j);swap(c[l], c[0]);
        for(int k : c) a.push_back(k);
    }
    auto L = fl(b);
    if(L.second.empty()){
        a.push_back(i);
        for(int k : L.first) a.push_back(k);
        a.push_back(j);
        for(int k : c) a.push_back(k);
        return {a, {}};
    } else {
        if(a.empty()){
            L.first.push_back(i);
            for(int k : L.second) L.first.push_back(k);
            L.first.push_back(j);
            for(int k : c) L.first.push_back(k);
            return {L.first, {}};
        }
        if(isg(a[0], L.first[0])){
            a.push_back(i);
            swap(a.back(), a[0]);
            for(int k : L.first) a.push_back(k);
            for(int k : a) L.second.push_back(k);
            L.second.push_back(j);
            for(int k : c) L.second.push_back(k);
            return {L.second, {}};
        } else {
            a.push_back(i);
            swap(a.back(), a[0]);
            for(int k : L.second) a.push_back(k);
            for(int k : a) L.first.push_back(k);
            L.first.push_back(j);
            for(int k : c) L.first.push_back(k);
            return {L.first, {}};
        }
    }

}
std::vector<int> longest_trip(int N, int D)
{
    vector<int> V;
    for(int i = 0;i < N;i++) {
        V.push_back(i);
        for(int j = 0;j < N;j++) g[i][j] = 0;
    }
    auto L = fl(V);
    if(L.first.size()>=L.second.size()) return L.first;
    return L.second;
}

Compilation message

longesttrip.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > fl(const std::vector<int>&)':
longesttrip.cpp:34:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(i = 1;i < V.size();i++){
      |               ~~^~~~~~~~~~
longesttrip.cpp:65:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |                 int m = r+l>>1;
      |                         ~^~
longesttrip.cpp:70:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |                 int m = ll+rr>>1;
      |                         ~~^~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Runtime error 11 ms 492 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 7 ms 344 KB Output is correct
3 Correct 6 ms 344 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 6 ms 344 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 7 ms 432 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 6 ms 344 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Incorrect 0 ms 344 KB invalid array
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 7 ms 344 KB Output is correct
3 Correct 7 ms 344 KB Output is correct
4 Correct 6 ms 464 KB Output is correct
5 Correct 7 ms 344 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Incorrect 1 ms 344 KB invalid array
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 596 KB Output is correct
2 Correct 7 ms 344 KB Output is correct
3 Correct 6 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Incorrect 1 ms 344 KB invalid array
8 Halted 0 ms 0 KB -