Submission #114218

#	Time	Username	Problem	Language	Result	Execution time	Memory
114218		evpipis	Port Facility (JOI17_port_facility)	C++17	22 / 100	6079 ms	366888 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;

const int len = 2e5+5, mod = 1e9+7;
int order[len], vis[len];
ii ran[len];
vector<int> adj[len], st;

int dfs(int u, int t){
    vis[u] = t;

    int ans = 1;
    for (int j = 0; j < adj[u].size(); j++){
        int v = adj[u][j];
        if (vis[v] == t)
            ans = 0;
        if (vis[v] == -1)
            ans *= dfs(v, 1-t);
    }

    //printf("dfs(%d, %d) = %d\n", u, t, ans);
    return ans;
}

int main(){
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        scanf("%d %d", &ran[i].fi, &ran[i].se);
        order[ran[i].fi] = -i;
        order[ran[i].se] = i;
    }

    for (int i = 1; i <= 2*n; i++){
        int cur = order[i];
        if (cur > 0){
            int pos = st.size()-1;
            while (st[pos] != cur){
                adj[cur].pb(st[pos]);
                adj[st[pos]].pb(cur);
                //printf("edge: %d, %d\n", cur, st[pos]);
                pos--;
            }

            st.erase(st.begin()+pos);
        }
        else{
            cur = -cur;
            st.pb(cur);
        }
    }

    for (int i = 1; i <= n; i++)
        vis[i] = -1;

    int po = 0, no = 0;
    for (int i = 1; i <= n; i++){
        if (vis[i] != -1)
            continue;

        if (dfs(i, 0))
            po++;
        else
            no = 1;
    }

    if (no){
        printf("0\n");
    }
    else{
        int temp = 1;
        for (int i = 0; i < po; i++)
            temp = (2*temp)%mod;
        printf("%d\n", temp);
    }
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int dfs(int, int)':
port_facility.cpp:19:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[u].size(); j++){
                     ~~^~~~~~~~~~~~~~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
port_facility.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &ran[i].fi, &ran[i].se);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22