oj.uz

Submission #720829

# Submission time Handle Problem Language Result Execution time Memory
720829 2023-04-09T11:54:42 Z lam Thousands Islands (IOI22_islands) C++17
1.75 / 100
 36 ms 6752 KB 
#include "islands.h"

#include <variant>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
#define ff first
#define ss second
const int maxn = 2010;
const int maxm = 3e5+10;
int n,m;
bool ban[maxm];
bool vis[maxn];
bool check = 1;
vector <int> path;
vector <ii> adj[maxn];
int l[maxn],t[maxn],cnt;
int bridge;

void dfs(int x, int goal)
{
    vis[x]=1;
    if (x==goal)
    {
        check=1;
        return;
    }
    for (ii i:adj[x])
    {
        if (ban[i.ss]||vis[i.ff]) continue;
        path.push_back(i.ss);
        dfs(i.ff,goal);
        if (check) return;
        path.pop_back();
    }
}

void dfs2(int x, int p)
{
    l[x]=t[x]=++cnt;
    for (ii i:adj[x])
    {
        if (p!=-1&&(i.ss/2)==(p/2)) continue;
        if (t[i.ff]==0)
        {
            dfs2(i.ff,i.ss);
            l[x]=min(l[x],l[i.ff]);
            if (l[i.ff] != t[i.ff])
            {
                bridge = i.ss;
            }
        }
        else l[x]=min(l[x],t[i.ff]);
    }
}

std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V) {
    n=N; m=M;
    for (int i=0; i<n; i++) adj[i].clear();
    fill_n(ban,m+1,0);
    path.clear();
    for (int i=0; i<m; i++)
    {
        int u=U[i]; int v=V[i];
        adj[u].push_back({v,i});
    }
    cnt=0;
    fill_n(l,n,0);
    fill_n(t,n,0);
    bridge = -1;
    dfs2(0,-1);
    if (bridge==-1) return false; //vector <int>({-1});
    fill_n(vis,n,0);
    int idx = (bridge/2)*2;
    ban[idx] = ban[idx+1] = 1;
    path.clear();
    check=0;
    dfs(0,U[idx]);
    vector <int> ans;
    for (int i:path) ans.push_back(i);
    ans.push_back(idx); ans.push_back(idx+1);
    reverse(path.begin(),path.end());
    for (int i:path) ans.push_back(i);
    path.clear();
    fill_n(vis,n,0);
    check=0;
    dfs(0,V[idx]);
    for (int i:path) ans.push_back(i);
    ans.push_back(idx); ans.push_back(idx+1);
    reverse(path.begin(),path.end());
    for (int i:path) ans.push_back(i);
    return ans;
}

//signed main()
//{
//    int n,m; cin>>n>>m;
//    vector <int> U,V;
//    for (int i=0; i<m; i++)
//    {
//        int u,v; cin>>u>>v;
//        U.push_back(u);
//        V.push_back(v);
//    }
//    vector <int> ans = find_journey(n,m,U,V);
//    for (int i:ans) cout<<i<<' '; cout<<endl;
//}
/**
6 12
1 0
0 1
2 0
0 2
2 5
5 2
0 3
3 0
4 2
2 4
4 2
2 4

**/

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
1.75 / 5.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 340 KB Output is partially correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 36 ms 6084 KB Output is correct

Subtask #3
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Partially correct 1 ms 340 KB Output is partially correct
5 Correct 1 ms 468 KB Output is correct
6 Partially correct 1 ms 356 KB Output is partially correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 340 KB Output is partially correct
2 Partially correct 1 ms 468 KB Output is partially correct
3 Partially correct 30 ms 6240 KB Output is partially correct
4 Partially correct 31 ms 6752 KB Output is partially correct
5 Partially correct 1 ms 500 KB Output is partially correct
6 Partially correct 2 ms 468 KB Output is partially correct
7 Partially correct 1 ms 340 KB Output is partially correct
8 Partially correct 1 ms 368 KB Output is partially correct
9 Partially correct 1 ms 364 KB Output is partially correct
10 Partially correct 1 ms 468 KB Output is partially correct
11 Incorrect 1 ms 468 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -