oj.uz

Submission #1100051

# Submission time Handle Problem Language Result Execution time Memory
1100051 2024-10-12T15:15:17 Z MMihalev Simurgh (IOI17_simurgh) C++14
0 / 100
 106 ms 3600 KB 
#include<iostream>
#include<algorithm>
#include<set>
#include<queue>
#include "simurgh.h"
using namespace std;
const int MAX_N=5e2+3;
const int MAX_M=125000;
int n,m;
int q;
vector<pair<int,int>>g[MAX_N];
vector<int>edges;
bool used[MAX_N];

bool stat[MAX_M];

void reset()
{
    edges.clear();
    for(int i=0;i<n;i++)
    {
        used[i]=0;
    }
}
void dfs(int u)
{
    used[u]=1;
    for(auto [v,edge]:g[u])
    {
        if(used[v])continue;
        edges.push_back(edge);
        dfs(v);
    }
}
vector<int> find_roads(int N, vector<int> u, vector<int> v)
{
    n=N;
    m=u.size();
    vector<int>ans;
    for(int i=0;i<m;i++)
    {
        g[u[i]].push_back({v[i],i});
        g[v[i]].push_back({u[i],i});
    }

    for(int u=0;u<n;u++)
    {
        vector<int>marked;
        bool changed=0;

        for(auto [v,edge]:g[u])
        {
            if(v<u)continue;
            reset();
            used[u]=1;
            dfs(v);
            edges.push_back(edge);
            marked.push_back(edge);
            break;
        }

        if(marked.size()==0)continue;

        int ma=count_common_roads(edges);q++;

        for(auto [v,edge]:g[u])
        {
            if(v<u)continue;
            if(edges.back()==edge)continue;

            edges.pop_back();
            edges.push_back(edge);
            int cur=count_common_roads(edges);q++;
            if(cur>ma)
            {
                marked.clear();
                changed=1;
                marked.push_back(edge);
                ma=cur;
            }
            else if(cur==ma)
            {
                marked.push_back(edge);
            }
        }

        if(changed)
        {
            for(int edge:marked)stat[edge]=1;
        }
        else
        {
            int forsure=-1;
            for(auto [v,edge]:g[u])
            {
                if(stat[edge])forsure=edge;
            }

            if(forsure==-1)
            {
                for(int edge:marked)stat[edge]=1;
            }
            else
            {
                edges.pop_back();
                edges.push_back(forsure);
                int forsuremax=count_common_roads(edges);q++;

                if(forsuremax==ma)for(int edge:marked)stat[edge]=1;
            }
        }
    }

    for(int i=0;i<m;i++)
    {
        if(stat[i])ans.push_back(i);
    }

    if(q>30000)while(1);

    return ans;
}

Compilation message

simurgh.cpp: In function 'void dfs(int)':
simurgh.cpp:28:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |     for(auto [v,edge]:g[u])
      |              ^
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:51:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |         for(auto [v,edge]:g[u])
      |                  ^
simurgh.cpp:66:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |         for(auto [v,edge]:g[u])
      |                  ^
simurgh.cpp:94:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   94 |             for(auto [v,edge]:g[u])
      |                      ^

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 1 ms 344 KB correct
4 Correct 0 ms 348 KB correct
5 Correct 0 ms 344 KB correct
6 Correct 0 ms 428 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 348 KB correct
9 Incorrect 1 ms 348 KB WA in grader: NO
10 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 1 ms 344 KB correct
4 Correct 0 ms 348 KB correct
5 Correct 0 ms 344 KB correct
6 Correct 0 ms 428 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 348 KB correct
9 Incorrect 1 ms 348 KB WA in grader: NO
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 1 ms 344 KB correct
4 Correct 0 ms 348 KB correct
5 Correct 0 ms 344 KB correct
6 Correct 0 ms 428 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 348 KB correct
9 Incorrect 1 ms 348 KB WA in grader: NO
10 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB correct
2 Correct 1 ms 348 KB correct
3 Incorrect 106 ms 3600 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 1 ms 344 KB correct
4 Correct 0 ms 348 KB correct
5 Correct 0 ms 344 KB correct
6 Correct 0 ms 428 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 348 KB correct
9 Incorrect 1 ms 348 KB WA in grader: NO
10 Halted 0 ms 0 KB -