Submission #869023

#	Time	Username	Problem	Language	Result	Execution time	Memory
869023		prohacker	Joker (BOI20_joker)	C++14	14 / 100	2100 ms	7612 KiB

Joker

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int,int>
#define mp make_pair

using namespace std;

const int N = 2e5+10;
const int INF = INT_MAX;
const int mod = 1e9+7;

int n,m,q;
pair<int,int> edges[N];
int color[N],lab[N];

void make_set() {
    for(int i = 1 ; i <= n ; i++) {
        lab[i] = i;
        color[i] = 0;
    }
}

pii Find(int u) {
    if(u == lab[u]) {
        return pii(u,color[u]);
    }
    pii p = Find(lab[u]);
    lab[u] = p.first;
    color[u] = (color[u]^p.second);
    return pii(lab[u],color[u]);
}

bool join(int u, int v, int c) {
    pii hihi = Find(u);
    pii hehe = Find(v);
    if(hihi.first == hehe.first) {
        if(hihi.second^hehe.second^c) {
            return false;
        }
        return true;
    }
    lab[hehe.first] = hihi.first;
    color[hehe.first] = (color[u]^color[v]^c);
    return true;
}

signed main()
{
    if (fopen("solve.inp", "r")) {
        freopen("solve.inp", "r", stdin);
        freopen("solve.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> q;
    for(int i = 1 ; i <= m ; i++) {
        int u,v; cin >> u >> v;
        edges[i] = {u,v};
    }
    while(q--) {
        int l,r; cin >> l >> r;
        make_set();
        for(int i = 1 ; i < l ; i++) {
            if(!join(edges[i].first,edges[i].second,1)) {
                goto done;
            }
        }
        for(int i = r+1 ; i <= m ; i++) {
            if(!join(edges[i].first,edges[i].second,1)) {
                goto done;
            }
        }
        cout << "NO" << '\n';
        continue;
        done:;
        cout << "YES" << '\n';
    }
    return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'int main()':
Joker.cpp:51:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         freopen("solve.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen("solve.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 0 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29