Submission #19,445

19445

2025-12-09 13:27:39

cpp17

Time limit exceeded 25/50

1.1s

1940 KiB

#include <iostream>
#include <stdint.h>

using namespace std;

bool pt[500][500];  // path to
bool pnt[500][500];

bool ty[500];
bool ptr(uint16_t x, uint16_t y, uint16_t n){
    if(pt[x][y]) return 1;
    if(pnt[x][y]) return 0;
    if(ty[x]) return 0;
    ty[x] = 1;

    for(uint16_t i=0; i<n; i++){
        if(!pt[x][i]) continue;
        if(ptr(i, y, n)) return pt[i][y] = pt[x][i] = pt[x][y] = 1;
    }
    pnt[x][y] = 1;
    return 0;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    uint16_t N;
    uint32_t Q;

    cin >> N >> Q;

    for(uint16_t i=0; i<N; i++) for(uint16_t j=0; j<N; j++) pt[i][j] = 0;
    bool nz = 0;
    
    while(Q--){
        char t;
        uint16_t x, y;
        cin >> t >> x >> y;
        x--; y--;
        
        if(t == '1'){
            pt[x][y] = 1;   // x->y
                        /// c->x->y
            for(uint16_t i=0; i<N; i++){
                if(pt[i][x]) pt[i][y] = 1;
                for(uint16_t j=0; j<N; j++) pnt[i][j] = 0;
            }
        }else if(t == '2'){
            for(uint16_t i=0; i<N; i++) ty[i] = 0;
            if(ptr(x, y, N)) cout << "IGEN";
            else cout << "NEM";
            cout << endl;
        }
    }
    return 0;
}

Subtask		Sum	Test	Verdict	Time	Memory
	subtask1	0/0
			1	Accepted	1ms	316 KiB
			2	Time limit exceeded	1.082s	1072 KiB
	subtask2	10/10
			3	Accepted	4ms	316 KiB
			4	Accepted	30ms	564 KiB
			5	Accepted	402ms	820 KiB
			6	Accepted	280ms	820 KiB
			7	Accepted	264ms	780 KiB
			8	Accepted	4ms	564 KiB
			9	Accepted	2ms	316 KiB
			10	Accepted	37ms	628 KiB
			11	Accepted	180ms	820 KiB
			12	Accepted	250ms	820 KiB
	subtask3	15/15
			13	Accepted	1ms	316 KiB
			14	Accepted	2ms	500 KiB
			15	Accepted	1ms	316 KiB
			16	Accepted	1ms	336 KiB
			17	Accepted	1ms	316 KiB
			18	Accepted	1ms	316 KiB
			19	Accepted	1ms	500 KiB
			20	Accepted	1ms	316 KiB
			21	Accepted	1ms	528 KiB
			22	Accepted	1ms	508 KiB
			23	Accepted	2ms	508 KiB
			24	Accepted	1ms	508 KiB
			25	Accepted	2ms	500 KiB
			26	Accepted	2ms	316 KiB
			27	Accepted	1ms	508 KiB
			28	Accepted	1ms	316 KiB
			29	Accepted	2ms	316 KiB
			30	Accepted	1ms	316 KiB
			31	Accepted	1ms	316 KiB
			32	Accepted	1ms	316 KiB
			33	Accepted	1ms	316 KiB
			34	Accepted	1ms	316 KiB
			35	Accepted	1ms	316 KiB
			36	Accepted	1ms	332 KiB
			37	Accepted	1ms	500 KiB
			38	Accepted	1ms	316 KiB
	subtask4	0/25
			39	Accepted	1ms	316 KiB
			40	Time limit exceeded	1.1s	1076 KiB
			41	Accepted	4ms	316 KiB
			42	Accepted	30ms	564 KiB
			43	Accepted	402ms	820 KiB
			44	Accepted	280ms	820 KiB
			45	Accepted	264ms	780 KiB
			46	Accepted	4ms	564 KiB
			47	Accepted	2ms	316 KiB
			48	Accepted	37ms	628 KiB
			49	Accepted	180ms	820 KiB
			50	Accepted	250ms	820 KiB
			51	Accepted	2ms	500 KiB
			52	Accepted	1ms	316 KiB
			53	Accepted	1ms	336 KiB
			54	Accepted	1ms	316 KiB
			55	Accepted	1ms	316 KiB
			56	Accepted	1ms	500 KiB
			57	Accepted	1ms	316 KiB
			58	Accepted	1ms	528 KiB
			59	Accepted	1ms	508 KiB
			60	Accepted	2ms	508 KiB
			61	Accepted	1ms	508 KiB
			62	Accepted	2ms	500 KiB
			63	Accepted	2ms	316 KiB
			64	Accepted	1ms	508 KiB
			65	Accepted	1ms	316 KiB
			66	Accepted	2ms	316 KiB
			67	Accepted	1ms	316 KiB
			68	Accepted	1ms	316 KiB
			69	Accepted	1ms	316 KiB
			70	Accepted	1ms	316 KiB
			71	Accepted	1ms	316 KiB
			72	Accepted	1ms	316 KiB
			73	Accepted	1ms	332 KiB
			74	Accepted	1ms	500 KiB
			75	Accepted	1ms	316 KiB
			76	Wrong answer	134ms	780 KiB
			77	Accepted	118ms	796 KiB
			78	Time limit exceeded	1.098s	1364 KiB
			79	Accepted	109ms	564 KiB
			80	Accepted	753ms	1076 KiB
			81	Wrong answer	126ms	832 KiB
			82	Accepted	165ms	880 KiB
			83	Accepted	238ms	756 KiB
			84	Accepted	421ms	820 KiB
			85	Time limit exceeded	1.018s	1076 KiB
			86	Accepted	266ms	1088 KiB
			87	Accepted	834ms	1076 KiB
			88	Accepted	206ms	824 KiB
			89	Accepted	293ms	820 KiB
			90	Accepted	423ms	1664 KiB
			91	Time limit exceeded	1.077s	820 KiB
			92	Accepted	418ms	1584 KiB
			93	Time limit exceeded	1.1s	820 KiB
			94	Accepted	421ms	1588 KiB
			95	Time limit exceeded	1.08s	1012 KiB
			96	Time limit exceeded	1.082s	820 KiB
			97	Time limit exceeded	1.09s	820 KiB
			98	Time limit exceeded	1.08s	908 KiB
			99	Time limit exceeded	1.077s	932 KiB
			100	Accepted	912ms	1736 KiB
			101	Accepted	943ms	1608 KiB
102	Time limit exceeded		1.049s	1840 KiB
103	Time limit exceeded		1.075s	1940 KiB
104	Accepted		897ms	1588 KiB