oj.uz

Submission #297858

# Submission time Handle Problem Language Result Execution time Memory
297858 2020-09-12T05:29:38 Z Autoratch Simurgh (IOI17_simurgh) C++14
0 / 100
 1 ms 384 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 501;

int n,m;
vector<pair<int,int> > adj[N];
vector<int> r,ans,tmp,ask;
bool visited[N];
vector<vector<int> > cmp;
int ed[N][N];
set<int> ts;

void dfs(int u,int f)
{
    if(visited[u]) return;
    visited[u] = true;
    tmp.push_back(u);
    for(auto [id,v] : adj[u]) if(!visited[v] and v!=f) r.push_back(id),dfs(v,f);
}

std::vector<int> find_roads(int _n, std::vector<int> u, std::vector<int> v) 
{
    n = _n,m = u.size();
    for(int i = 0;i < n;i++) for(int j = 0;j < n;j++) ed[i][j] = -1;
    for(int i = 0;i < m;i++)
    {
        int a = u[i],b = v[i];
        adj[a].push_back({i,b});
        adj[b].push_back({i,a});
        ed[a][b] = ed[b][a] = i;
    }
    for(int i = 0;i < n;i++)
    {
        r.clear();
        tmp.clear();
        cmp.clear();
        for(int j = 0;j < n;j++) visited[j] = false;
        for(int j = 0;j < n;j++) if(!visited[j] and j!=i) dfs(j,i),cmp.push_back(tmp),tmp.clear();
        int cm = cmp.size();
        for(int j = 0;j < cm;j++) 
        {
            tmp.clear();
            for(int x : cmp[j]) if(ed[i][x]!=-1) tmp.push_back(ed[i][x]);
            swap(cmp[j],tmp);
        }
        for(int j = 0;j < cm;j++) 
        {
            tmp.clear();
            tmp = r;
            for(int k = 0;k < cm;k++) if(k!=j) tmp.push_back(cmp[k][0]);
            int mx = -1,id;
            for(int x : cmp[j])
            {
                ask = tmp;
                ask.push_back(x);
                int ret = count_common_roads(ask);
                if(ret>mx) mx = ret,id = x;
            }
            ts.insert(id);
        }        
    }
    for(int x : ts) ans.push_back(x);
    return ans;
}

Compilation message

simurgh.cpp: In function 'void dfs(int, int)':
simurgh.cpp:20:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |     for(auto [id,v] : adj[u]) if(!visited[v] and v!=f) r.push_back(id),dfs(v,f);
      |              ^

Subtask #1
0 / 13.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB correct
2 Incorrect 1 ms 384 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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