제출 #815176

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
815176		jajco	Jail (JOI22_jail)	C++17	0 / 100	13 ms	648 KiB

jail

#include <ios>
#include <set>
#include <vector>
#include <algorithm>
#include <functional>
#define REP(i, n) for (int i=0; i<n; ++i)
typedef std::vector <int> vi;
int main(){
    int q;
    scanf("%d", &q);
    while (q--){
        int n;
        scanf("%d", &n);
        std::vector <vi> pol(n+1, vi());
        bool liniow=1;
        REP(i, n-1){ // wczytanie grafu
            int p,k;
            scanf("%d%d", &p, &k);
            if (p!=k-1)
                liniow=0;
            pol[p].emplace_back(k);
            pol[k].emplace_back(p);
        }
        vi gl(n+1),ojc(n+1);
        { // glebokosci
            std::function <void(int, int, int)> DFS=[&](
                    int i, int o, int g){
                ojc[i]=o;
                gl[i]=g;
                for (int j : pol[i])
                    if (j!=o)
                        DFS(j, i, g+1);
            };
            DFS(1, 0, 1);
        }
        int m;
        scanf("%d", &m);
        vi pocz(m),kon(m),perm,pn(n+1, -1),kn(n+1, -1);
        REP(i, m){ // wczytanie ziomow
            scanf("%d%d", &pocz[i], &kon[i]);
            pn[pocz[i]]=i,kn[kon[i]]=i;
        }
        std::vector <vi> dag(m, vi());
        vi ile(m);
        bool czy;
        if (liniow){
            std::set <int> v,rv;
            czy=1;
            REP(i, m){
                if (pocz[i]<kon[i]){
                    v.insert(pocz[i]);
                    v.insert(kon[i]);
                }
                else{
                    rv.insert(pocz[i]);
                    rv.insert(kon[i]);
                }
            }
            REP(i, m){
                if (pocz[i]<kon[i]){
                    auto itr=rv.lower_bound(pocz[i]);
                    if (itr!=rv.end()&&*itr<=kon[i])
                        czy=0;
                }
                else{
                    auto itr=v.lower_bound(pocz[i]);
                    if (itr!=v.end()&&*itr<=kon[i])
                        czy=0;
                }
            }
            goto fin;
        }
        {
            auto mkkraw=[&](int i, int id){
                if (pn[i]>=0&&pn[i]!=id) // musimy byc po nim
                    dag[pn[i]].emplace_back(id),++ile[id];
                if (kn[i]>=0&&kn[i]!=id) // musimy byc przed nim
                    dag[id].emplace_back(kn[i]),++ile[kn[i]];
            };
            if (m<=500)
                REP(k, m){ // generacja daga dfsami
                    static std::function <
                            bool(int, int, int, int)> DFS=[&](
                            int i, int ojc, int d, int id){
                        bool r=i==d;
                        if (!r)
                            for (int j : pol[i])
                                if (j!=ojc)
                                    if (r|=DFS(j, i, d, id))
                                        break;
                        if (r)
                            mkkraw(i, id);
                        return r;
                    };
                    DFS(pocz[k], pocz[k], kon[k], k);
                }
            else{
                REP(i, m){ // generacja daga idac w gore do LCA
                    int p=pocz[i],k=kon[i];
                    if (gl[p]>gl[k])
                        std::swap(p, k);
                    while (p!=k){ // p ma mniejsze gl
                        if (gl[p]==gl[k])
                            mkkraw(p, i),p=ojc[p];
                        else
                            mkkraw(k, i),k=ojc[k];
                    }
                    mkkraw(p, i);
                }
            }
            { // check daga
                vi zer;
                REP(i, m)
                    if (!ile[i])
                        zer.emplace_back(i);
                int w=0;
                while (zer.size()){
                    ++w;
                    int p=zer.back();
                    zer.pop_back();
                    for (int i : dag[p])
                        if (!--ile[i])
                            zer.emplace_back(i);
                }
                czy=w==m;
            }
        }
        fin:
        printf(czy ? "Yes\n" : "No\n");
    }
}	

컴파일 시 표준 에러 (stderr) 메시지

jail.cpp: In function 'int main()':
jail.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
jail.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
jail.cpp:18:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |             scanf("%d%d", &p, &k);
      |             ~~~~~^~~~~~~~~~~~~~~~
jail.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d", &m);
      |         ~~~~~^~~~~~~~~~
jail.cpp:40:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |             scanf("%d%d", &pocz[i], &kon[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23